Cod sursa(job #2426799)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 29 mai 2019 13:06:51
Problema Gossips Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
using namespace std;

const int DIM = 100005;

struct Node {
	set<int> set1, set2; } segmentTree[DIM * 4];

int first[DIM], last[DIM], degree[DIM];
vector<int> edge[DIM];

void dfs(int x) {
	static int counter = 0;

	first[x] = ++counter;
	for (int y : edge[x]) {
		dfs(y); }
	last[x] = counter; } 

bool solve(set<int> &mySet, int minim, int maxim) {
	set<int> :: iterator it = mySet.lower_bound(minim);
	return it != mySet.end() and *it <= maxim; }

void update(int node, int left, int right, int _left, int _right, int position) {	
	
	segmentTree[node].set1.insert(position);
	if (_left <= left and right <= _right) {
		segmentTree[node].set2.insert(position); return; }
	
	int middle = (left + right) / 2;
	
	if (_left <= middle) {
		update(node * 2, left, middle, _left, _right, position); }
	if (middle < _right) {
		update(node * 2 + 1, middle + 1, right, _left, _right, position); } } 

bool query(int node, int left, int right, int _left, int _right, int minim, int maxim) {
	
	if (solve(segmentTree[node].set2, minim, maxim)) {
		return true; }
	if (_left <= left and right <= _right) {
		return solve(segmentTree[node].set1, minim, maxim); }
	
	int middle = (left + right) / 2;
	
	if (_left <= middle and query(node * 2, left, middle, _left, _right, minim, maxim)) {
		return true; }
	if (middle < _right and query(node * 2 + 1, middle + 1, right, _left, _right, minim, maxim)) {
		return true; }
	return false; }

int main(void) {
	
	freopen("gossips.in", "r", stdin);
	freopen("gossips.out", "w", stdout);
	
	int n, m, q; 
	cin >> n >> m >> q;

	for (int i = 1; i <= m; ++i) {
		int x, y;
		cin >> x >> y;

		edge[x].push_back(y);
		++degree[y]; }

	for (int i = 1; i <= n; ++i) {
		if (!degree[i]) {
			dfs(i); } }

	while (q--) {
		int t, x, y;
		cin >> t >> x >> y;

		if (t == 2) {
			update(1, 1, n, first[x], last[x], first[y]); }
		else {
			cout << (query(1, 1, n, first[x], last[x], first[y], last[y]) ? "YES" : "NO") << "\n"; } }

	return 0; }