Cod sursa(job #1550519)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 13 decembrie 2015 20:27:03
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#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_1{
	int n;
	vector<set<tuple<int, int>>> buf;
public:
	set_aint_1(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>(*it) <= get<1>(t)){
				return true; } }
		return false; } };

class set_aint_2{
	int n;
	vector<set<tuple<int, int>>> buf;
	bool check(const int nod, const tuple<int, int> t){
		auto it = buf[nod].lower_bound(t);
		return it != end(buf[nod]) && get<1>(*it) <= get<1>(t); }
public:
	set_aint_2(const int N): n(N), buf(2*n){}
	void update(int poz, const tuple<int, int> t){
		for(poz += n; poz > 0; poz /= 2){
			buf[poz].insert(t); } }
	bool query(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 && check(st++, t)){
				return true; }
			if(dr%2 == 1 && check(--dr, 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_1 sa1(get<1>(st_fin[0])+1);
	set_aint_2 sa2(get<1>(st_fin[0])+1);

	for(int i = 0, s, x, y; i < q; ++i){
		f >> s >> x >> y;
		if(s == 1){
			if(sa1.query(get<0>(st_fin[x]), st_fin[y]) || sa2.query(get<0>(st_fin[x]), get<1>(st_fin[x]), st_fin[y])){
				g << "YES\n"; }
			else{
				g << "NO\n"; } }
		else{
			sa1.update(get<0>(st_fin[x]), get<1>(st_fin[x]), st_fin[y]);
			sa2.update(get<0>(st_fin[x]), st_fin[y]); } }
	return 0; }