oj.uz

답안 #760631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -