Mai intai trebuie sa te autentifici.
Cod sursa(job #2131845)
Utilizator | Data | 15 februarie 2018 00:12:05 | |
---|---|---|---|
Problema | Gossips | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.01 kb |
#include <bits/stdc++.h>
#define MAXN 100000
std::vector <int> G[1 + MAXN];
int in[1 + MAXN];
bool seen[1 + MAXN];
int first[1 + MAXN], last[1 + MAXN], ind;
inline void dfs(int node){
seen[node] = 1;
first[node] = ++ind;
for(auto y: G[node]) if(!seen[y]) dfs(y);
last[node] = ind;
}
std::set <int> S[1 + 4 * MAXN], T[1 + 4 * MAXN];
int left, right, pos, val, ans;
void update(int p, int st, int dr){
T[p].insert(first[val]);
if(left <= st && dr <= right) S[p].insert(first[val]);
else{
int m = (st + dr) / 2;
if(left <= m) update(2 * p, st, m);
if(m + 1 <= right) update(2 * p + 1, m + 1, dr);
}
}
void query(int p, int st, int dr){
if(ans) return;
if(S[p].size()){
int a = first[val], b = last[val];
auto it1 = S[p].lower_bound(a);
if(it1 != S[p].end() && *it1 <= b) ans = true;
}
if(left <= st && dr <= right){
if(T[p].size()){
int a = first[val], b = last[val];
auto it3 = T[p].lower_bound(a);
if(it3 != T[p].end() && *it3 <= b) ans = true;
}
}
else{
int m = (st + dr) / 2;
if(left <= m) query(2 * p, st, m);
if(m + 1 <= right) query(2 * p + 1, m + 1, dr);
}
}
int main(){
FILE*fi,*fo;
fi = fopen("gossips.in","r");
fo = fopen("gossips.out","w");
int n, m, q;
fscanf(fi,"%d%d%d", &n, &m, &q);
for(int i = 1; i <= m; i++){
int x, y;
fscanf(fi,"%d%d", &x, &y);
G[x].push_back(y);
in[y]++;
}
for(int i = 1; i <= n; i++) if(!in[i]) dfs(i);
for(int i = 1; i <= q; i++){
int type, x, y;
fscanf(fi,"%d%d%d", &type, &x, &y);
left = first[x];
right = last[x];
val = y;
if(type == 2) update(1, 1, n);
else{
ans = false;
query(1, 1, n);
if(ans) fprintf(fo,"YES\n");
else fprintf(fo,"NO\n");
}
}
return 0;
}