oj.uz

Submission #16982

# Submission time Handle Problem Language Result Execution time Memory
16982 2015-11-03T14:09:54 Z erdemkiraz Tropical Garden (IOI11_garden) C++
69 / 100
 236 ms 35180 KB 
#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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14712 KB Output is correct
2 Correct 15 ms 14684 KB Output is correct
3 Correct 16 ms 14632 KB Output is correct
4 Correct 18 ms 14548 KB Output is correct
5 Correct 15 ms 14448 KB Output is correct
6 Correct 16 ms 14792 KB Output is correct
7 Correct 15 ms 14572 KB Output is correct
8 Correct 16 ms 14556 KB Output is correct
9 Correct 18 ms 14748 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14712 KB Output is correct
2 Correct 15 ms 14684 KB Output is correct
3 Correct 16 ms 14632 KB Output is correct
4 Correct 18 ms 14548 KB Output is correct
5 Correct 15 ms 14448 KB Output is correct
6 Correct 16 ms 14792 KB Output is correct
7 Correct 15 ms 14572 KB Output is correct
8 Correct 16 ms 14556 KB Output is correct
9 Correct 18 ms 14748 KB Output is correct
10 Correct 15 ms 14432 KB Output is correct
11 Correct 31 ms 17800 KB Output is correct
12 Correct 62 ms 20032 KB Output is correct
13 Correct 68 ms 29508 KB Output is correct
14 Correct 222 ms 33272 KB Output is correct
15 Correct 236 ms 33548 KB Output is correct
16 Correct 169 ms 27876 KB Output is correct
17 Correct 149 ms 25860 KB Output is correct
18 Correct 58 ms 19988 KB Output is correct
19 Correct 211 ms 33256 KB Output is correct
20 Correct 224 ms 33564 KB Output is correct
21 Correct 172 ms 27820 KB Output is correct
22 Correct 146 ms 25904 KB Output is correct
23 Correct 222 ms 35180 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14712 KB Output is correct
2 Correct 15 ms 14684 KB Output is correct
3 Correct 16 ms 14632 KB Output is correct
4 Correct 18 ms 14548 KB Output is correct
5 Correct 15 ms 14448 KB Output is correct
6 Correct 16 ms 14792 KB Output is correct
7 Correct 15 ms 14572 KB Output is correct
8 Correct 16 ms 14556 KB Output is correct
9 Correct 18 ms 14748 KB Output is correct
10 Correct 15 ms 14432 KB Output is correct
11 Correct 31 ms 17800 KB Output is correct
12 Correct 62 ms 20032 KB Output is correct
13 Correct 68 ms 29508 KB Output is correct
14 Correct 222 ms 33272 KB Output is correct
15 Correct 236 ms 33548 KB Output is correct
16 Correct 169 ms 27876 KB Output is correct
17 Correct 149 ms 25860 KB Output is correct
18 Correct 58 ms 19988 KB Output is correct
19 Correct 211 ms 33256 KB Output is correct
20 Correct 224 ms 33564 KB Output is correct
21 Correct 172 ms 27820 KB Output is correct
22 Correct 146 ms 25904 KB Output is correct
23 Correct 222 ms 35180 KB Output is correct
24 Incorrect 17 ms 14456 KB Output isn't correct
25 Halted 0 ms 0 KB -