Submission #16984

#	Time	Username	Problem	Language	Result	Execution time	Memory
16984		erdemkiraz	Tropical Garden (IOI11_garden)	C++98	100 / 100	4623 ms	40484 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 3e5 + 5;

int n, m, p;
bool was[N], h[N];
int go[N];
vector < int > come[N];
vector < ii > v[N];

vector < int > cycle;

int findCycle(int x) {
	h[x] = 1;
	cycle.push_back(x);
	if(!h[go[x]])
		return findCycle(go[x]);
	return go[x];
}

int curOut, curSize, cycleCnt, tme;
int out[N], dep[N], cycleSize[N], whichCycle[N], st[N], nd[N], onCycle[N];

void dfs(int x, int d) {
	h[x] = 1;
	st[x] = ++tme;
	whichCycle[x] = cycleCnt;
	out[x] = curOut;
	dep[x] = d;
	cycleSize[x] = curSize;
	foreach(it, come[x]) {
		int u = *it;
		if(!h[u])
			dfs(u, d + 1);
	}
	nd[x] = tme;	
}

void init() {
	for(int i = 1; i <= n; i++) {
		for(int it = 0; it < v[i].size(); it++) {
			int u = v[i][it].first;
			int e =	v[i][it].second;
			was[i + (it * n)] = 1;
			if(e == v[u][0].second and v[u].size() > 1) {
				go[i + (it * n)] = u + n;
				come[u + n].push_back(i + (it * n));
			}
			else {
				go[i + (it * n)] = u;
				come[u].push_back(i + (it * n));
			}
		}
	}
	for(int i = 1; i <= 2 * n; i++) {
		//printf("go[%d] = %d\n", i, go[i]);
	}
	for(int i = 1; i <= 2 * n; i++)
		onCycle[i] = -1;
	for(int i = 1; i <= 2 * n; i++) {
		if(was[i] and !h[i]) {
			cycleCnt++;
			cycle.clear();
			int cyc = findCycle(i);
			foreach(it, cycle) {
				int x = *it;
				h[x] = 0;
			}
			reverse(cycle.begin(), cycle.end());
			while(cycle.back() != cyc)
				cycle.pop_back();
			reverse(cycle.begin(), cycle.end());
			for(int it = 0; it < cycle.size(); it++) {
				onCycle[cycle[it]] = it;
			}
			foreach(it, cycle) {
				int x = *it;
				h[x] = 1;
			}
			curSize = cycle.size();
			foreach(it, cycle) {
				int x = *it;
				curOut = x;
				dfs(x, 0);
			}
		}
	}
}

bool check(int x, int y, int k) {
	if(whichCycle[x] != whichCycle[y])
		return 0;
	if(onCycle[y] == -1) {
		if(out[x] == out[y] and st[y] <= st[x] and st[x] <= nd[y])
			return dep[x] - dep[y] == k;
		return 0;
	}
	int dist = dep[x], size = cycleSize[x];
	x = out[x];
	x = onCycle[x];
	y = onCycle[y];
	if(x <= y)
		dist += y - x;
	else
		dist += size - x + y;
	if(dist > k)
		return 0;
	return (k - dist) % size == 0;
}

int solve(int x) {
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		bool flag = 0;
		flag |= check(i, p, x);
		if(was[p + n])
			flag |= check(i, p + n, x);
		ans += flag;
	}
	return ans;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n = N;
	m = M;
	p = P + 1;
	for(int i = 0; i < M; i++) {
		int x = R[i][0] + 1;
		int y = R[i][1] + 1;
		if(v[x].size() < 2)
			v[x].push_back(ii(y, i));
		if(v[y].size() < 2)
			v[y].push_back(ii(x, i));
	}
	init();
	for(int i = 0; i < Q; i++) {
		answer(solve(G[i]));
	}
}

Compilation message (stderr)

garden.cpp: In function 'void init()':
garden.cpp:54:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int it = 0; it < v[i].size(); it++) {
                   ~~~^~~~~~~~~~~~~
garden.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int it = 0; it < cycle.size(); it++) {
                    ~~~^~~~~~~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31