Cod sursa(job #1900619)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 3 martie 2017 15:22:38
Problema Gossips Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>

const int kMaxDim = 100005;

struct SegTreeNode {
	std::set< int > data;
	std::set< int > extra;
};

enum Operation {
	query = 1,
	update = 2
};

SegTreeNode segTree[kMaxDim << 2];

int degree[kMaxDim];
std::vector< int > sons[kMaxDim];

int start[kMaxDim], finish[kMaxDim], currIndex;

void DfsInit(int node) {
	start[node] = ++currIndex;

	for (int son : sons[node])
		DfsInit(son);

	finish[node] = currIndex;
}

void SegTreeUpdate(int node, int left, int right, int uLeft, int uRight, int value) {
	if (uLeft <= left && right <= uRight) {
		segTree[node].data.insert(value);
		segTree[node].extra.insert(value);
		return;
	}

	int middle = (left + right) / 2;
	if (middle >= uLeft)
		SegTreeUpdate(2*node, left, middle, uLeft, uRight, value);
	if (middle < uRight)
		SegTreeUpdate(2*node + 1, middle + 1, right, uLeft, uRight, value);

	segTree[node].data.insert(value);
}

bool FindFromInterval(int minimum, int maximum, std::set< int >& valueSet) {
	std::set< int >::iterator it = valueSet.lower_bound(minimum);

	if (it == valueSet.end() || *it > maximum)
		return false;
	else
		return true;
}

bool SegTreeQuery(int node, int left, int right, int qLeft, int qRight, int minToFind, int maxToFind) {
	if (qLeft <= left && right <= qRight)
		return FindFromInterval(minToFind, maxToFind, segTree[node].data);

	if (FindFromInterval(minToFind, maxToFind, segTree[node].extra))
		return true;

	bool res = false;
	int middle = (left + right) / 2;

	if (qLeft <= middle)
		res |= SegTreeQuery(2*node, left, middle, qLeft, qRight, minToFind, maxToFind);
	if (res)
		return true;
	if (middle < qRight)
		res |= SegTreeQuery(2*node + 1, middle + 1, right, qLeft, qRight, minToFind, maxToFind);
	return res;
}

int main() {
	std::ifstream inputFile("gossips.in");
	std::ofstream outputFile("gossips.out");

	int nodeCount, edgesCount, queryCount;
	inputFile >> nodeCount >> edgesCount >> queryCount;

	for (int i = 1; i <= edgesCount; ++i) {
		int x, y;
		inputFile >> x >> y;
		sons[x].push_back(y);
		degree[y]++;
	}

	for (int i = 1; i <= nodeCount; ++i)
		if (degree[i] == 0)
			DfsInit(i);

	for (int i = 1; i <= queryCount; ++i) {
		int operation;
		inputFile >> operation;

		if (operation == update) {
			int x, y;
			inputFile >> x >> y;

			SegTreeUpdate(1, 1, nodeCount, start[x], finish[x], start[y]);
		}
		else {
			int x, y;
			inputFile >> x >> y;

			outputFile << (SegTreeQuery(1, 1, nodeCount, start[x], finish[x], start[y], finish[y]) ? "YES" : "NO");
			outputFile << '\n';
		}
	}

	inputFile.close();
	outputFile.close();

	return 0;
}

//Trust me, I'm the Doctor!