oj.uz

Submission #534942

# Submission time Handle Problem Language Result Execution time Memory
534942 2022-03-09T07:41:50 Z shrimb Tropical Garden (IOI11_garden) C++17
49 / 100
 160 ms 70336 KB 
#include "garden.h"
#include "gardenlib.h"
#include"bits/stdc++.h"
using namespace std;

int nxt[100001][2];
int dp[100001][2][32];


void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	for (int i = 0 ; i < M ; i++) {
		auto [u, v] = R[i];
		u++, v++;
		if (!nxt[u][0] and !nxt[v][0]) {
			nxt[u][0] = -v;
			nxt[v][0] = -u;
		}
		if (!nxt[u][0]) nxt[u][0] = v;
		if (!nxt[v][0]) nxt[v][0] = u;

		if (abs(nxt[u][0]) != v and nxt[u][1] == 0) {
			if (abs(nxt[v][0]) == u) nxt[u][1] = -v;
			else nxt[u][1] = v;
		}

		if (abs(nxt[v][0]) != u and nxt[v][1] == 0) {
			if (abs(nxt[u][0]) == v) nxt[v][1] = -u;
			else nxt[v][1] = u;
		}
	}

	for (int i = 1 ; i <= N ; i++) {
		if (nxt[i][1] == 0) nxt[i][1] = nxt[i][0];
	}

	// for (int i = 1 ; i <= N ; i++) {
	// 	cout << i << ": " << nxt[i][0] << " " << nxt[i][1] << endl;
	// }

	for (int j = 0 ; j < 32 ; j++) {
		for (int i = 1 ; i <= N ; i++) {
			for (int k = 0 ; k < 2 ; k++) {
				if (j == 0) {
					dp[i][k][j] = nxt[i][k];
				} else {
					int x = dp[i][k][j-1];
					int u = abs(x);
					int v = x < 0;
					dp[i][k][j] = dp[u][v][j-1];
				}
			}
		}
	}

	for (int q = 0 ; q < Q ; q++) {
		int k = G[q];
		int ans = 0;
		for (int i = 1 ; i <= N ; i++) {
			int u = i, v = 0;
			for (int j = 31 ; j >= 0 ; j--) {
				if (k & (1 << j)) {
					int x = dp[u][v][j];
					u = abs(x);
					v = x < 0;
				}
			}
			// cerr << q << ": " << i << " " << u << endl;
			if (u == P + 1) {
				ans++;
			}
		}
		answer(ans);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 564 KB Output is correct
7 Correct 1 ms 284 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 3 ms 700 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 564 KB Output is correct
7 Correct 1 ms 284 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 16 ms 6476 KB Output is correct
12 Correct 38 ms 10880 KB Output is correct
13 Correct 160 ms 23956 KB Output is correct
14 Runtime error 102 ms 70336 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 564 KB Output is correct
7 Correct 1 ms 284 KB Output is correct
8 Correct 2 ms 560 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 16 ms 6476 KB Output is correct
12 Correct 38 ms 10880 KB Output is correct
13 Correct 160 ms 23956 KB Output is correct
14 Runtime error 102 ms 70336 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -