Cod sursa(job #850366)

Utilizator stoicatheoFlirk Navok stoicatheo Data 8 ianuarie 2013 13:25:12
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
# include <algorithm>
# include <cstdio>
# include <set>
# include <vector>
using namespace std;
 
const char *FIN = "gossips.in", *FOU = "gossips.out";
const int MAX = 100005;
 
int N, M, Q, T[MAX], back[MAX], front[MAX];
set <int> ai[2][MAX << 2];
vector <int> G[MAX];
 
void dfs (int S) {
    back[S] = ++back[0];
    for (typeof (G[0].end ()) it = G[S].begin (); it != G[S].end (); ++it) {
        if (back[*it]) continue;
        dfs (*it);
    }
    front[S] = back[0];
}
 
void update (int nod, int st, int dr, int s1, int s2, int val) {
    ai[0][nod].insert (val);
    if (s1 <= st && dr <= s2) {
        ai[1][nod].insert (val);
        return ;
    }
    int mij = st + dr >> 1;
    if (s1 <= mij) update (nod << 1, st, mij, s1, s2, val);
    if (mij <  s2) update (nod << 1 | 1, mij + 1, dr, s1, s2, val);
}
 
int query (int nod, int st, int dr, int X1, int X2, int Y1, int Y2) {
    set <int> :: iterator it = ai[1][nod].lower_bound (Y1);
    if (it != ai[1][nod].end () && *it <= Y2) return 1;
    if ((it = ai[0][nod].lower_bound (Y1)) != ai[0][nod].end () && *it <= Y2) {
        if (X1 <= st && dr <= X2) return 1;
        int mij = st + dr >> 1;
        if (X1 <= mij && query (nod << 1, st, mij, X1, X2, Y1, Y2)) return 1;
        if (mij < X2) return query (nod << 1 | 1, mij + 1, dr, X1, X2, Y1, Y2);
    }
    return 0;
}
 
int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);
 
    scanf ("%d %d %d", &N, &M, &Q);
    for (int i = 1, x, y; i <= M; ++i) {
        scanf ("%d %d", &x, &y);
        G[x].push_back (y), T[y] = x;
    }
    for (int i = 1; i <= N; ++i) {
        if (T[i]) continue;
        dfs (i);
    }
    for (int i = 1, z, x, y; i <= Q; ++i) {
        scanf ("%d %d %d", &z, &x, &y);
        if (z == 2) {
            update (1, 1, N, back[x], front[x], back[y]);
        } else {
            fputs (query (1, 1, N, back[x], front[x], back[y], front[y]) ? "YES\n" : "NO\n", stdout);
        }
    }
}