oj.uz

Submission #760630

# Submission time Handle Problem Language Result Execution time Memory
760630 2023-06-18T04:29:10 Z SanguineChameleon Tropical Garden (IOI11_garden) C++17
49 / 100
 15 ms 15668 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) / k + 1) * k;
				}
				if (G[i] >= maxN * 2) {
					exit(0);
				}
				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 6212 KB Output is correct
6 Correct 4 ms 6292 KB Output is correct
7 Correct 3 ms 6100 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 4 ms 6612 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 6212 KB Output is correct
6 Correct 4 ms 6292 KB Output is correct
7 Correct 3 ms 6100 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 4 ms 6612 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Runtime error 15 ms 15668 KB Execution killed with signal 8
12 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 6212 KB Output is correct
6 Correct 4 ms 6292 KB Output is correct
7 Correct 3 ms 6100 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 4 ms 6612 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Runtime error 15 ms 15668 KB Execution killed with signal 8
12 Halted 0 ms 0 KB -