Cod sursa(job #1550465)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 13 decembrie 2015 19:30:27
Problema Gossips Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 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++; }

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<int> nume(n+1, 0);
	for(int i = 1; i <= n; ++i){
		if(tata[i] != 0){
			continue; }
		vector<int> st = {i};
		nume[i] = i;
		while(!st.empty()){
			const int cur = st.back();
			st.pop_back();
			for(const auto next : copii[cur]){
				nume[next] = nume[cur];
				st.push_back(next); } } }

	vector<tuple<int, int>> st_fin(n+1);
	{
		int p = 0;
		dfs(0, copii, st_fin, p); }

	vector<set<tuple<int, int>>> ce_stie_nume(n+1);

	for(int i = 0, s, x, y; i < q; ++i){
		f >> s >> x >> y;
		if(s == 1){
			auto it = ce_stie_nume[nume[x]].lower_bound(st_fin[y]);
			if(it != end(ce_stie_nume[nume[x]]) && get<1>(*it) <= get<1>(st_fin[y])){
				g << "YES\n"; }
			else{
				g << "NO\n"; } }
		else{
			ce_stie_nume[nume[x]].insert(st_fin[y]); } }
	return 0; }