oj.uz

Submission #760631

# Submission time Handle Problem Language Result Execution time Memory
760631 2023-06-18T04:29:39 Z SanguineChameleon Tropical Garden (IOI11_garden) C++17
49 / 100
 54 ms 19788 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1.5e5 + 20;
vector<int> adj[maxN];
int nxt[maxN * 2];
int dist[maxN * 2][2];
int cnt[maxN * 2][2];
int cycle[2];
int dest;

void dfs(int u, int k) {
	if (u == dest) {
		dist[u][k] = 0;
		return;
	}
	dist[u][k] = -2;
	int v = nxt[u];
	if (dist[v][k] == -2) {
		dist[u][k] = -1;
		return;
	}
	else if (dist[v][k] == -3) {
		dfs(v, k);
	}
	if (dist[v][k] == -1) {
		dist[u][k] = -1;
		return;
	}
	else {
		dist[u][k] = dist[v][k] + 1;
		return;
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	for (int i = 0; i < M; i++) {
		int u = R[i][0];
		int v = R[i][1];
		adj[u].push_back(i << 1);
		adj[v].push_back(i << 1 | 1);
	}
	for (int i = 0; i < N; i++) {
		if ((int)adj[i].size() == 1) {
			nxt[adj[i][0] ^ 1] = adj[i][0];
		}
		else {
			nxt[adj[i][0] ^ 1] = adj[i][1];
			for (int j = 1; j < (int)adj[i].size(); j++) {
				nxt[adj[i][j] ^ 1] = adj[i][0];
			}
		}
	}
	for (int k = 0; k < min(2, (int)adj[P].size()); k++) {
		dest = adj[P][k];
		for (int i = 0; i < M * 2; i++) {
			dist[i][k] = -3;
		}
		for (int i = 0; i < M * 2; i++) {
			if (dist[i][k] == -3) {
				dfs(i, k);
			}
		}
		cycle[k] = (dist[nxt[dest]][k] == -1 ? -1 : dist[nxt[dest]][k] + 1);
		for (int i = 0; i < N; i++) {
			int start = adj[i][0];
			if (dist[start][k] != -1) {
				cnt[dist[start][k]][k]++;
			}
		}
		if (cycle[k] != -1) {
			for (int i = cycle[k]; i < maxN * 2; i++) {
				cnt[i][k] += cnt[i - cycle[k]][k];
			}
		}
	}
	for (int i = 0; i < Q; i++) {
		int res = 0;
		for (int k = 0; k < min(2, (int)adj[P].size()); k++) {
			if (cycle[k] == -1) {
				if (G[i] < maxN * 2) {
					res += cnt[G[i]][k];
				}
			}
			else {
				if (G[i] >= maxN * 2) {
					G[i] -= ((G[i] - maxN * 2) / cycle[k] + 1) * cycle[k];
				}
				res += cnt[G[i]][k];
			}
		}
		answer(res);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 ms 6100 KB Output is correct
5 Correct 3 ms 6100 KB Output is correct
6 Correct 3 ms 6356 KB Output is correct
7 Correct 4 ms 6100 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 6 ms 6592 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 ms 6100 KB Output is correct
5 Correct 3 ms 6100 KB Output is correct
6 Correct 3 ms 6356 KB Output is correct
7 Correct 4 ms 6100 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 6 ms 6592 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Correct 12 ms 7760 KB Output is correct
12 Correct 18 ms 9984 KB Output is correct
13 Correct 29 ms 19788 KB Output is correct
14 Correct 48 ms 16664 KB Output is correct
15 Correct 49 ms 17024 KB Output is correct
16 Correct 45 ms 15432 KB Output is correct
17 Correct 44 ms 15012 KB Output is correct
18 Correct 17 ms 7432 KB Output is correct
19 Correct 48 ms 16620 KB Output is correct
20 Correct 54 ms 17076 KB Output is correct
21 Correct 45 ms 15308 KB Output is correct
22 Incorrect 50 ms 14924 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 ms 6100 KB Output is correct
5 Correct 3 ms 6100 KB Output is correct
6 Correct 3 ms 6356 KB Output is correct
7 Correct 4 ms 6100 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 6 ms 6592 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Correct 12 ms 7760 KB Output is correct
12 Correct 18 ms 9984 KB Output is correct
13 Correct 29 ms 19788 KB Output is correct
14 Correct 48 ms 16664 KB Output is correct
15 Correct 49 ms 17024 KB Output is correct
16 Correct 45 ms 15432 KB Output is correct
17 Correct 44 ms 15012 KB Output is correct
18 Correct 17 ms 7432 KB Output is correct
19 Correct 48 ms 16620 KB Output is correct
20 Correct 54 ms 17076 KB Output is correct
21 Correct 45 ms 15308 KB Output is correct
22 Incorrect 50 ms 14924 KB Output isn't correct
23 Halted 0 ms 0 KB -