Pagini recente » Cod sursa (job #1959144) | Cod sursa (job #2698341) | Cod sursa (job #80357) | Cod sursa (job #1185608) | Cod sursa (job #792860)
Cod sursa(job #792860)
#include<fstream>
#include<vector>
#include<set>
using namespace std;
ifstream in("gossips.in");
ofstream out("gossips.out");
const int N = 100100;
int n, nr, m, q, ver[N], l[N], r[N], px, py, val, vx, vy;
vector<int> v[N];
set<int> arbPart[3*N], arbAll[3*N];
void dfs(int nod) {
l[nod] = ++nr;
for(vector<int>::iterator it = v[nod].begin(); it!=v[nod].end(); ++it)
dfs(*it);
r[nod] = nr;
}
void update(int nod, int pozx, int pozy) {
arbPart[nod].insert(val);
if(px <= pozx && pozy <= py) {
arbAll[nod].insert(val);
return;
}
int mid = (pozx + pozy)/2;
if(mid >= px)
update(2 * nod, pozx, mid);
if(mid < py)
update(2 * nod + 1, mid + 1, pozy);
}
bool query(int nod, int pozx, int pozy) {
set<int>::iterator it = arbAll[nod].lower_bound(vx);
if(it != arbAll[nod].end() && (*it) <= vy)
return true;
it = arbPart[nod].lower_bound(vx);
if(it != arbPart[nod].end() && (*it) <= vy) {
int mid = (pozx + pozy)/2;
if(px <= pozx && pozy <= py)
return true;
if(mid >= px)
if(query(2 * nod, pozx, mid))
return true;
if(mid < py)
return query(2 * nod + 1, mid + 1, pozy);
}
return false;
}
int main() {
int i, a, b, op, x, y;
in >> n >> m >> q;
for(i = 1; i<=m; ++i) {
in >> a >> b;
ver[b] = true;
v[a].push_back(b);
}
for(i = 1; i<=n; ++i) if(!ver[i])
dfs(i);
for(i = 1; i<=q; ++i) {
in >> op >> x >> y;
if(op == 1) {
px = l[x]; py = r[x];
vx = l[y]; vy = r[y];
out << (query(1, 1, n) ? "YES\n" : "NO\n");
}
else {
px = l[x]; py = r[x]; val = l[y];
update(1, 1, n);
}
}
return 0;
}