Cod sursa(job #2028855)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 28 septembrie 2017 19:14:00
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <fstream>
#include <set>
#include <vector>

using namespace std;

ifstream fin ("gossips.in"); ofstream fout ("gossips.out");

const int nmax = 1e5;

bool viz[nmax + 1], intra[nmax + 1];
int ind_dfs, limx, limy;
int first[nmax + 1], last[nmax + 1];

set< int > aintjos[4 * nmax + 1], aintsus[4 * nmax + 1];
vector< int > g[nmax + 1];

void dfs (int nod) {
    viz[ nod ] = 1;
    ++ ind_dfs;
    first[ nod ] = ind_dfs;

    for (auto i : g[ nod ]) {
        if (viz[ i ] == 0) {
            dfs( i );
        }
    }

    last[ nod ] = ind_dfs;
}

void updatesus (int nod, int x, int y, int st, int dr, int val) {
    if (st <= x && y <= dr) {
        aintsus[ nod ].insert( val );
        return ;
    }

    int mij = (x + y) / 2;
    if (st <= mij)
        updatesus(2 * nod, x, mij, st, dr, val);
    if (mij < dr)
        updatesus(2 * nod + 1, mij + 1, y, st, dr, val);
}

void updatejos (int nod, int x, int y, int pos, int val) {
    aintjos[ nod ].insert( val );

    if (x == y) {
        return ;
    }

    int mij = (x + y) / 2;
    if (pos <= mij)
        updatejos(2 * nod, x, mij, pos, val);
    else
        updatejos(2 * nod + 1, mij + 1, y, pos, val);
}

inline bool ok (const set< int > &s) {
    set< int >::iterator it = s.lower_bound( limx );

    if (it != s.end() && *it <= limy) {
        return 1;
    }
    return 0;
}

bool querysus (int nod, int x, int y, int pos) {
    if (ok(aintsus[ nod ]))
        return 1;

    if (x == y)
        return 0;

    int mij = (x + y) / 2;
    if (pos <= mij)
        return querysus(2 * nod, x, mij, pos);
    else
        return querysus(2 * nod + 1, mij + 1, y, pos);
}

bool queryjos (int nod, int x, int y, int st, int dr) {
    if (st <= x && y <= dr) {
        return ok(aintjos[ nod ]);
    }

    int mij = (x + y) / 2;
    bool sol = 0;
    if (st <= mij) {
        sol = queryjos(2 * nod, x, mij, st, dr);
    }

    if (mij < dr && sol == 0) {
        sol = queryjos(2 * nod + 1, mij + 1, y, st, dr);
    }
    return sol;
}

int main() {
    int n, m, q;
    fin >> n >> m >> q;

    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;
        g[ x ].push_back( y );
        intra[ y ] = 1;
    }

    for (int i = 1; i <= n; ++ i) {
        if (viz[ i ] == 0 && intra[ i ] == 0) {
            dfs( i );
        }
    }

    while (q --) {
        int t, x, y;
        fin >> t >> x >> y;

        if (t == 2) {
            updatesus(1, 1, n, first[ x ], last[ x ], first[ y ]);
            updatejos(1, 1, n, first[ x ], first[ y ]);
        } else {
            limx = first[ y ];
            limy = last[ y ];

            bool ans = queryjos(1, 1, n, first[ x ], last[ x ]);

            if (ans == 0) {
                ans = querysus(1, 1, n, first[ x ]);
            }

            fout << (ans == 1 ? "YES\n" : "NO\n");
        }
    }

    fin.close();
    fout.close();
    return 0;
}