Submission #287757

#	Time	Username	Problem	Language	Result	Execution time	Memory
287757		shrek12357	Gondola (IOI14_gondola)	C++14	Compilation error	0 ms	0 KiB

gondola

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include <stack>
using namespace std;

#define MAXN 10005

int par[MAXN];
int depth[MAXN];
int anc[MAXN][20];
bool vis[MAXN];
vector<stack<int>> found(MAXN);
vector<vector<int>> adjList(MAXN);
vector<vector<pair<int, int>>> queries(MAXN);
map<pair<pair<int, int>, int>, bool> answers;
vector<int> types(MAXN);

void dfs(int src) {
	vis[src] = true;
	for (auto p : adjList[src]) {
		if (vis[p])
			continue;
		par[p] = src;
		anc[p][0] = src;
		depth[p] = depth[src] + 1;
		dfs(p);
	}
}

int LCA(int a, int b) {
	if (depth[a] < depth[b]) {
		swap(a, b);
	}
	int K = depth[a] - depth[b];
	for (int k = 0; k < 20; k++) {
		if (K & (1 << k)) {
			a = anc[a][k];
		}
	}
	if (a == b) {
		return a;
	}
	for (int i = 19; i >= 0; i--) {
		if (anc[a][i] != anc[b][i]) {
			a = anc[a][i];
			b = anc[b][i];
		}
	}
	return anc[a][0];
}

void dfs2(int src) {
	found[types[src]].push(src);
	for (auto p : queries[src]) {
		int node = LCA(src, p.first);
		stack<int> temp = found[p.second];
		if (temp.size() == 0 || depth[node] > depth[temp.top()]) {
			answers[make_pair(make_pair(src, p.first), p.second)] = false;
		}
		else {
			answers[make_pair(make_pair(src, p.first), p.second)] = true;
		}
	}
	for (auto p : adjList[src]) {
		if (p != par[src]) {
			dfs2(p);
		}
	}
	found[types[src]].pop();
}

int main() {
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		types[i + 1] = temp;
	}
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		adjList[a].push_back(b);
		adjList[b].push_back(a);
	}
	vector<pair<pair<int, int>, int>> q;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		queries[a].push_back(make_pair(b, c));
		queries[b].push_back(make_pair(a, c));
		q.push_back(make_pair(make_pair(a, b), c));
	}
	par[1] = 1;
	anc[1][0] = 1;
	depth[1] = 0;
	dfs(1);
	for (int k = 1; k < 20; k++) {
		for (int i = 1; i <= n; i++) {
			anc[i][k] = anc[anc[i][k - 1]][k - 1];
		}
	}

	dfs2(1);
	string ans = "";
	for (auto p : q) {
		if (answers[p] || answers[make_pair(make_pair(p.first.second, p.first.first), p.second)]) {
			ans += "1";
		}
		else {
			ans += "0";
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

/tmp/ccPPzXg4.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc4NUFvR.o:gondola.cpp:(.text.startup+0x0): first defined here
/tmp/ccPPzXg4.o: In function `main':
grader.cpp:(.text.startup+0xa2): undefined reference to `valid'
grader.cpp:(.text.startup+0xee): undefined reference to `countReplacement'
grader.cpp:(.text.startup+0x112): undefined reference to `replacement'
collect2: error: ld returned 1 exit status