Cod sursa(job #2085552)

Utilizator amaliarebAmalia Rebegea amaliareb Data 10 decembrie 2017 13:28:35
Problema Gossips Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define iter set<pair<int, int> >:: iterator

using namespace std;
ifstream f("gossips.in");
ofstream g("gossips.out");
const int MaxN = 100005;
int n, m, q, lini[2 * MaxN], n2, fth[MaxN];
pair<int, int> interv[MaxN];
vector<int> gr[MaxN];
set<pair<int, int> > aint[8 * MaxN];

inline iter mergge(iter it, set<pair<int, int> > s)
{
    iter it2 = it;
    ++it2;
    int st = it->first;
    int dr = it2->second;
    s.erase(it);
    s.erase(it2);
    iter ret = s.insert({st, dr}).first;
    return ret;
}

void dfs(int node)
{
    interv[node].first = ++n2;
    //g << node << ' ';
    for (auto son: gr[node])
        if (!interv[son].first) dfs(son);
    interv[node].second = ++n2;
    //g << node << ' ';
}

inline void update(int node, int l, int r, int poz, int updl, int updr)
{
    int mid = (l + r) / 2;
    if (l != r && poz <= mid) update(2 * node, l, mid, poz, updl, updr);
    else if(l != r) update(2 * node + 1, mid + 1, r, poz, updl, updr);
    iter it = aint[node].insert({updl, updr}).first;
    if (it != aint[node].begin())
    {
        iter it2 = it;
        it2--;
        if(it2->second >= it->first - 1) it = mergge(it2, aint[node]);
    }
    if (++it != aint[node].end())
    {
        iter it2 = it;
        it2--;
        if(it2->second >= it->first - 1) it = mergge(it2, aint[node]);
    }
}

inline bool query(int node, int l, int r, int ql, int qr, int a)
{
    int mid = (l + r) / 2;
    bool ok = 0;
    if (l >= ql && r <= qr)
    {
        if (aint[node].empty()) return 0;
        iter it = aint[node].lower_bound({interv[a].first, 0});
        if (it != aint[node].end() && it->first >= interv[a].first && it->second <= interv[a].second) ok = 1;
        if (it != aint[node].begin() && (it == aint[node].end() || it->first > interv[a].first)) --it;
        if (it->first <= interv[a].first && it->second >= interv[a].first) ok = 1;
        return ok;
    }
    if (ql <= mid) ok = ok | query(2 * node, l, mid, ql, qr, a);
    if (qr > mid) ok = ok | query(2 * node + 1, mid + 1, r, ql, qr, a);
    return ok;
}

int main()
{
    f >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        fth[y] = x;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) if (!fth[i]) dfs(i);
    for (; q > 0; --q)
    {
        int tip, a, b;
        f >> tip >> a >> b;
        if (tip == 1)
        {
            if (query(1, 1, n2, interv[b].first, interv[b].second, a)) g << "YES\n";
            else g << "NO\n";
        }
        else update(1, 1, n2, interv[b].first, interv[a].first, interv[a].second);
    }
    return 0;
}