oj.uz

Submission #39298

# Submission time Handle Problem Language Result Execution time Memory
39298 2018-01-11T03:45:22 Z 14kg Tropical Garden (IOI11_garden) C++11
69 / 100
 50 ms 7644 KB 
#include "garden.h"
#include "gardenlib.h"
#include <algorithm>
#include <vector>
#define N 150001
#define MP 23

using namespace std;
int n, m, start, cycle1_len, cycle2_len;
int Sx, Sy, d[N][2], d1[N][2], d2[N][2];
pair<int, int> r[N];

void Push_r(int x, int y) {
	if (!r[x].first) r[x].first = y;
	else if (!r[x].second) r[x].second = y;
}
int dfs(int x, int y, int len) {
	d[x][y] = len;
	int nx = y ? r[x].second : r[x].first;
	int ny = r[nx].second && r[nx].first == x ? 1 : 0;

	if (d[nx][ny]) {
		if (d[nx][ny] == 1) return len;
		else return -1;
	}
	return dfs(nx, ny, len + 1);
}
int dfs_find1(int x, int y) {
	if (x == start && y == 0) return 0;
	if (d1[x][y] != 0) return d1[x][y];

	int nx = y ? r[x].second : r[x].first;
	int ny = r[nx].second && r[nx].first == x ? 1 : 0;

	d1[x][y] = -1, d1[x][y] = dfs_find1(nx, ny);
	if (d1[x][y] >= 0) d1[x][y]++;

	return d1[x][y];
}
int dfs_find2(int x, int y) {
	if (x == start && y == 1) return 0;
	if (d2[x][y] != 0) return d2[x][y];

	int nx = y ? r[x].second : r[x].first;
	int ny = r[nx].second && r[nx].first == x ? 1 : 0;

	d2[x][y] = -1, d2[x][y] = dfs_find2(nx, ny);
	if (d2[x][y] >= 0) d2[x][y]++;

	return d2[x][y];
}
void count_routes(int _n, int _m, int _s, int _r[][2], int Q_len, int Q[]) {
	n = _n, start = _s + 1;
	for (int i = 0; i < _m; i++) {
		int x = _r[i][0] + 1, y = _r[i][1] + 1;
		Push_r(x, y), Push_r(y, x);
	}

	cycle1_len = dfs(start, 0, 1);
	for (int i = 1; i <= n; i++) d[i][0] = d[i][1] = 0;
	cycle2_len = dfs(start, 1, 1);
	for (int i = 1; i <= n; i++) d[i][0] = d[i][1] = 0;
	
	for (int i = 1; i <= n; i++) {
		if (d1[i][0] == 0) dfs_find1(i, 0);
		if (d2[i][0] == 0) dfs_find2(i, 0);
		if (i == start) d1[i][0] = d2[i][0] = 0;
	}

	for (int i = 0; i < Q_len; i++) {
		int res = 0;
		if (Q[i] == 0) { answer(1); continue; }
		for (int j = 1; j <= n; j++) {
			if ((d1[j][0] > 0 || j == start) && cycle1_len > 0 && Q[i] >= d1[j][0] && (Q[i] - d1[j][0]) % cycle1_len == 0) res++;// , printf("%d %d\n", d1[j][0], cycle1_len);
			else if ((d2[j][0] > 0 || j == start) && cycle2_len > 0 && Q[i] >= d2[j][0] && (Q[i] - d2[j][0]) % cycle2_len == 0) res++;// , printf("%d %d\n", d2[j][0], cycle2_len);
		} answer(res);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 352 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 356 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 448 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 352 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 356 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 448 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 9 ms 1512 KB Output is correct
12 Correct 17 ms 2540 KB Output is correct
13 Correct 31 ms 7260 KB Output is correct
14 Correct 47 ms 7056 KB Output is correct
15 Correct 47 ms 7068 KB Output is correct
16 Correct 41 ms 5724 KB Output is correct
17 Correct 40 ms 5268 KB Output is correct
18 Correct 18 ms 2436 KB Output is correct
19 Correct 46 ms 6980 KB Output is correct
20 Correct 50 ms 7140 KB Output is correct
21 Correct 44 ms 5624 KB Output is correct
22 Correct 44 ms 5116 KB Output is correct
23 Correct 48 ms 7644 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 352 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 356 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 448 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 9 ms 1512 KB Output is correct
12 Correct 17 ms 2540 KB Output is correct
13 Correct 31 ms 7260 KB Output is correct
14 Correct 47 ms 7056 KB Output is correct
15 Correct 47 ms 7068 KB Output is correct
16 Correct 41 ms 5724 KB Output is correct
17 Correct 40 ms 5268 KB Output is correct
18 Correct 18 ms 2436 KB Output is correct
19 Correct 46 ms 6980 KB Output is correct
20 Correct 50 ms 7140 KB Output is correct
21 Correct 44 ms 5624 KB Output is correct
22 Correct 44 ms 5116 KB Output is correct
23 Correct 48 ms 7644 KB Output is correct
24 Incorrect 3 ms 376 KB Output isn't correct
25 Halted 0 ms 0 KB -