Pagini recente » Cod sursa (job #2792915) | Cod sursa (job #2982725) | Cod sursa (job #396715) | Cod sursa (job #481096) | Cod sursa (job #1550512)
#include <fstream>
#include <iostream>
#include <vector>
#include <tuple>
#include <set>
using namespace std;
void dfs(const int cur, const vector<vector<int>>& copii, vector<tuple<int, int>>& st_fin, int& p){
get<0>(st_fin[cur]) = ++p;
for(const auto next : copii[cur]){
dfs(next, copii, st_fin, p); }
get<1>(st_fin[cur]) = p; }
class set_aint{
int n;
vector<set<tuple<int, int>>> buf;
public:
set_aint(const int N): n(N), buf(2*n){}
void update(int st, int dr, const tuple<int, int> t){
for(st += n, dr += n+1; st < dr; st /= 2, dr /= 2){
if(st%2 == 1){
buf[st++].insert(t); }
if(dr%2 == 1){
buf[--dr].insert(t); } } }
bool query(int poz, const tuple<int, int> t){
for(poz += n; poz > 0; poz /= 2){
auto it = buf[poz].lower_bound(t);
if(it != end(buf[poz]) && get<1>(*buf[poz].lower_bound(t)) <= get<1>(t)){
return true; } }
return false; } };
int main(){
ifstream f("gossips.in");
ofstream g("gossips.out");
int n, m, q;
f >> n >> m >> q;
vector<int> tata(n+1, 0);
vector<vector<int>> copii(n+1);
for(int i = 0, a, b; i < m; ++i){
f >> a >> b;
tata[b] = a; }
for(int i = 1; i <= n; ++i){
copii[tata[i]].push_back(i); }
vector<tuple<int, int>> st_fin(n+1);
{
int p = -1;
dfs(0, copii, st_fin, p); }
set_aint sa(get<1>(st_fin[0])+1);
for(int i = 0, s, x, y; i < q; ++i){
f >> s >> x >> y;
if(s == 1){
if(sa.query(get<0>(st_fin[x]), st_fin[y])){
g << "YES\n"; }
else{
g << "NO\n"; } }
else{
sa.update(get<0>(st_fin[x]), get<1>(st_fin[x]), st_fin[y]); } }
return 0; }