Cod sursa(job #2426800)

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

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
 
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
 
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
} in("gossips.in");

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.out", "w", stdout);
	
	int n, m, q; 
	in >> n >> m >> q;

	for (int i = 1; i <= m; ++i) {
		int x, y;
		in >> 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;
		in >> 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; }