oj.uz

Submission #1087250

# Submission time Handle Problem Language Result Execution time Memory
1087250 2024-09-12T11:28:58 Z dubabuba Tropical Garden (IOI11_garden) C++14
100 / 100
 1233 ms 44156 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

const int mxn = 1.5e5 + 1000;
const int MXN = 3e5 + 100000;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

vector<int> adj[mxn]; // OG graph
vector<int> rev[MXN]; // buba graph
int nxt[MXN];
bool vis[MXN];

bool fake(int cur, int prv) {
	if(adj[cur].size() == 1) return 0;
	return prv == adj[cur][0];
}

void build_buba(int cur, int prv = -1) {
	int bu = cur + mxn * fake(cur, prv);

	if(vis[bu]) return;
	vis[bu] = 1;
	
	int sus = 0;
	if(adj[cur].size() == 1) sus = adj[cur][0];
	else if(prv == adj[cur][0]) sus = adj[cur][1];
	else sus = adj[cur][0];

	int bv = sus + mxn * fake(sus, cur);
	nxt[bu] = bv;
	rev[bv].push_back(bu);

	build_buba(sus, cur);
}

vector<int> dis(MXN, -1);
vector<int> fdis(MXN, -1);
void bfs(int P, vector<int> &dis) {
	priority_queue<pii> pq;
	pq.push(MP(0, P));

	while(pq.size()) {
		int d = -pq.top().ff;
		int u = pq.top().ss;
		pq.pop();

		if(dis[u] > -1) continue;
		dis[u] = d;

		for(int v : rev[u])
			if(dis[v] == -1)
				pq.push(MP(-d-1, v));
	}
}

int cyc(int P) {
	for(int i = 0; i < MXN; i++)
		vis[i] = 0;

	int cur = P, cnt = 0;
	vector<int> path;
	while(!vis[cur]) {
		vis[cur] = 1;
		path.push_back(cur);
		cur = nxt[cur];
	}

	while(path.back() != cur) {
		path.pop_back();
		cnt++;
	}

	if(cur != P) return 0;
	return cnt + 1;
}

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(v);
		adj[v].push_back(u);
	}

	memset(nxt, -1, sizeof nxt);
	for(int i = 0; i < N; i++)
		build_buba(i, -1);
	memset(vis, 0, sizeof vis);
	
	
	int in1 = cyc(P);
	int in2 = cyc(P + mxn);

	bfs(P, dis);
	bfs(P + mxn, fdis);

	auto sus1 = [&] (int u, int D) -> bool {
		if(dis[u] == -1) return 0;
		if(dis[u] == D) return 1;
		if(dis[u] > D) return 0;
		return in1 && ((D - dis[u]) % in1 == 0);
	};

	auto sus2 = [&] (int u, int D) -> bool {
		if(fdis[u] == -1) return 0;
		if(fdis[u] == D) return 1;
		if(fdis[u] > D) return 0;
		return in2 && ((D - fdis[u]) % in2 == 0);
	};

	for(int i = 0; i < Q; i++) {
		int D = G[i], ans = 0;
		for(int u = 0; u < N; u++) {
			if(sus1(u, D) || sus2(u, D)) {
				ans++;
			}
		}
		answer(ans);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18520 KB Output is correct
2 Correct 7 ms 18524 KB Output is correct
3 Correct 7 ms 18524 KB Output is correct
4 Correct 7 ms 18268 KB Output is correct
5 Correct 7 ms 18268 KB Output is correct
6 Correct 7 ms 18476 KB Output is correct
7 Correct 9 ms 18268 KB Output is correct
8 Correct 8 ms 18524 KB Output is correct
9 Correct 8 ms 18616 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18520 KB Output is correct
2 Correct 7 ms 18524 KB Output is correct
3 Correct 7 ms 18524 KB Output is correct
4 Correct 7 ms 18268 KB Output is correct
5 Correct 7 ms 18268 KB Output is correct
6 Correct 7 ms 18476 KB Output is correct
7 Correct 9 ms 18268 KB Output is correct
8 Correct 8 ms 18524 KB Output is correct
9 Correct 8 ms 18616 KB Output is correct
10 Correct 7 ms 18264 KB Output is correct
11 Correct 13 ms 20716 KB Output is correct
12 Correct 22 ms 21724 KB Output is correct
13 Correct 45 ms 37600 KB Output is correct
14 Correct 58 ms 27856 KB Output is correct
15 Correct 72 ms 27988 KB Output is correct
16 Correct 59 ms 26352 KB Output is correct
17 Correct 51 ms 25100 KB Output is correct
18 Correct 23 ms 21340 KB Output is correct
19 Correct 57 ms 27772 KB Output is correct
20 Correct 71 ms 27980 KB Output is correct
21 Correct 60 ms 26192 KB Output is correct
22 Correct 66 ms 25912 KB Output is correct
23 Correct 59 ms 29264 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18520 KB Output is correct
2 Correct 7 ms 18524 KB Output is correct
3 Correct 7 ms 18524 KB Output is correct
4 Correct 7 ms 18268 KB Output is correct
5 Correct 7 ms 18268 KB Output is correct
6 Correct 7 ms 18476 KB Output is correct
7 Correct 9 ms 18268 KB Output is correct
8 Correct 8 ms 18524 KB Output is correct
9 Correct 8 ms 18616 KB Output is correct
10 Correct 7 ms 18264 KB Output is correct
11 Correct 13 ms 20716 KB Output is correct
12 Correct 22 ms 21724 KB Output is correct
13 Correct 45 ms 37600 KB Output is correct
14 Correct 58 ms 27856 KB Output is correct
15 Correct 72 ms 27988 KB Output is correct
16 Correct 59 ms 26352 KB Output is correct
17 Correct 51 ms 25100 KB Output is correct
18 Correct 23 ms 21340 KB Output is correct
19 Correct 57 ms 27772 KB Output is correct
20 Correct 71 ms 27980 KB Output is correct
21 Correct 60 ms 26192 KB Output is correct
22 Correct 66 ms 25912 KB Output is correct
23 Correct 59 ms 29264 KB Output is correct
24 Correct 8 ms 18520 KB Output is correct
25 Correct 69 ms 20572 KB Output is correct
26 Correct 110 ms 21596 KB Output is correct
27 Correct 713 ms 37680 KB Output is correct
28 Correct 695 ms 27924 KB Output is correct
29 Correct 801 ms 28448 KB Output is correct
30 Correct 414 ms 25940 KB Output is correct
31 Correct 456 ms 25168 KB Output is correct
32 Correct 117 ms 21596 KB Output is correct
33 Correct 709 ms 27768 KB Output is correct
34 Correct 782 ms 28240 KB Output is correct
35 Correct 459 ms 26192 KB Output is correct
36 Correct 799 ms 25940 KB Output is correct
37 Correct 539 ms 29264 KB Output is correct
38 Correct 1233 ms 44156 KB Output is correct