Pagini recente » Cod sursa (job #1604094) | Cod sursa (job #678738) | Istoria paginii runda/porc_revelion | Cod sursa (job #2079209) | Cod sursa (job #987888)
Cod sursa(job #987888)
#include <fstream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int N, M, Q;
vector<int> V[100002];
int in[100002], out[100002], isnow;
bool isson[100002];
set<int> ARB[4 * 200002], T[4 * 200002];
int Ap1, Ap2, Av, Ar1, Ar2, Ar;
void update(int nod, int i1, int i2)
{
T[nod].insert(Av);
if (Ap1 <= i1 && i2 <= Ap2)
{
ARB[nod].insert(Av);
return;
}
int mid = (i1 + i2) / 2;
if (Ap1 <= mid) update(nod * 2, i1, mid);
if (Ap2 > mid) update(nod * 2 + 1, mid + 1, i2);
}
void query(int nod, int i1, int i2)
{
set<int>::iterator it = ARB[nod].lower_bound(Ar1);
if (it != ARB[nod].end() && *it <= Ar2)
{
Ar = 1;
return;
}
if (i1 == i2 || T[nod].lower_bound(Ar1) == T[nod].end() || (*T[nod].lower_bound(Ar1)) > Ar2) return;
int mid = (i1 + i2) / 2;
if (Ap1 <= mid) query(nod * 2, i1, mid);
if (Ap2 > mid && !Ar) query(nod * 2 + 1, mid + 1, i2);
}
void Dfs(int x)
{
in[x] = ++isnow;
for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
Dfs(*it);
out[x] = ++isnow;
}
int main()
{
ifstream fin("gossips.in");
ofstream fout("gossips.out");
fin >> N >> M >> Q;
for (int i = 1, nod1, nod2; i <= M; ++i)
{
fin >> nod1 >> nod2;
V[nod1].push_back(nod2);
isson[nod2] = true;
}
for (int i = 1; i <= N; ++i)
if (!isson[i])
Dfs(i);
for (int i = 1, type, val1, val2; i <= Q; ++i)
{
fin >> type >> val1 >> val2;
if (type == 1)
{
Ap1 = in[val1], Ap2 = out[val1], Ar1 = in[val2], Ar2 = out[val2], Ar = 0;
query(1, 1, 2 * N);
if (Ar) fout << "YES\n";
else fout << "NO\n";
}
else
{
Ap1 = in[val1], Ap2 = out[val1], Av = in[val2];
update(1, 1, 2 * N);
}
}
fin.close();
fout.close();
}