oj.uz

Submission #580910

# Submission time Handle Problem Language Result Execution time Memory
580910 2022-06-22T05:59:01 Z benson1029 Tropical Garden (IOI11_garden) C++14
100 / 100
 177 ms 92180 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;

vector< int > edg[700005];

int n;
int nxt[700005];
vector<int> p[700005];
bool vis1[700005], vis2[700005];
int dis1[700005], dis2[700005];
vector<int> ans1[700005], ans2[700005];
vector<int> cycle;
int mod1, mod2;

void rdfs1(int x, int dis) {
	if(x<n) ans1[dis%mod1].push_back(dis);
	for(int i:p[x]) {
		if(vis1[i]) continue;
		rdfs1(i, dis+1);
	}
}

void rdfs2(int x, int dis) {
	if(x<n) ans2[dis%mod2].push_back(dis);
	for(int i:p[x]) {
		if(vis2[i]) continue;
		rdfs2(i, dis+1);
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	n = N;
	for(int i=0; i<M; i++) {
		edg[R[i][0]].push_back(R[i][1]);
		edg[R[i][1]].push_back(R[i][0]);
	}
	for(int i=0; i<2*N; i++) {
		int dest;
		if(i<N) {
			dest = edg[i][0];
		}
		else {
			if(edg[i%N].size()==1) dest = -1;
			else dest = edg[i%N][1];
		}
		if(dest!=-1 && i%N == edg[dest][0] && edg[dest].size()>1) dest+=N;
		nxt[i] = dest;
		if(dest!=-1) p[dest].push_back(i);
	}
	int ptr = P;
	int tmp = 0;
	if(nxt[ptr] != -1) {
		while(!vis1[ptr]) {
			vis1[ptr] = true;
			dis1[ptr] = tmp;
			ptr = nxt[ptr];
			tmp++;
		}
		if(ptr != P) { // non-cyclic case
			for(int i=0; i<2*N; i++) vis1[i] = false;
			vis1[P] = true;
			mod1 = 2e9;
			rdfs1(P, 0);
		} else {
			mod1 = tmp;
			for(int i=0; i<2*N; i++) {
				if(vis1[i]) rdfs1(i, (mod1-dis1[i])%mod1);
			}
		}
	}

	ptr = P+n;
	tmp = 0;
	while(!vis2[ptr]) {
		vis2[ptr] = true;
		dis2[ptr] = tmp;
		ptr = nxt[ptr];
		tmp++;
	}
	if(ptr != P+n) {
		for(int i=0; i<2*N; i++) vis2[i] = false;
		vis2[P+n] = true;
		mod2 = 2e9;
		rdfs2(P+n, 0);
	} else {
		mod2 = tmp;
		for(int i=0; i<2*N; i++) {
			if(vis2[i]) rdfs2(i, (mod2-dis2[i])%mod2);
		}
	}

	for(int i=0; i<=4*n; i++) {
		sort(ans1[i].begin(), ans1[i].end());
		sort(ans2[i].begin(), ans2[i].end());
	}

	for(int i=0; i<Q; i++) {
		int g = G[i];
		int ans = 0;
		if(g%mod1 < 4*n)
			ans += upper_bound(ans1[g%mod1].begin(), ans1[g%mod1].end(), g) - ans1[g%mod1].begin();
		if(g%mod2 < 4*n)
			ans += upper_bound(ans2[g%mod2].begin(), ans2[g%mod2].end(), g) - ans2[g%mod2].begin();
		answer(ans);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 66260 KB Output is correct
2 Correct 35 ms 66180 KB Output is correct
3 Correct 32 ms 66168 KB Output is correct
4 Correct 33 ms 66032 KB Output is correct
5 Correct 35 ms 66092 KB Output is correct
6 Correct 32 ms 66260 KB Output is correct
7 Correct 32 ms 66120 KB Output is correct
8 Correct 42 ms 66192 KB Output is correct
9 Correct 35 ms 66260 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 66260 KB Output is correct
2 Correct 35 ms 66180 KB Output is correct
3 Correct 32 ms 66168 KB Output is correct
4 Correct 33 ms 66032 KB Output is correct
5 Correct 35 ms 66092 KB Output is correct
6 Correct 32 ms 66260 KB Output is correct
7 Correct 32 ms 66120 KB Output is correct
8 Correct 42 ms 66192 KB Output is correct
9 Correct 35 ms 66260 KB Output is correct
10 Correct 34 ms 66004 KB Output is correct
11 Correct 42 ms 68052 KB Output is correct
12 Correct 56 ms 69392 KB Output is correct
13 Correct 79 ms 82336 KB Output is correct
14 Correct 129 ms 77176 KB Output is correct
15 Correct 177 ms 77884 KB Output is correct
16 Correct 120 ms 74904 KB Output is correct
17 Correct 110 ms 74128 KB Output is correct
18 Correct 63 ms 70352 KB Output is correct
19 Correct 164 ms 78788 KB Output is correct
20 Correct 158 ms 79604 KB Output is correct
21 Correct 152 ms 76888 KB Output is correct
22 Correct 141 ms 75692 KB Output is correct
23 Correct 135 ms 79948 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 66260 KB Output is correct
2 Correct 35 ms 66180 KB Output is correct
3 Correct 32 ms 66168 KB Output is correct
4 Correct 33 ms 66032 KB Output is correct
5 Correct 35 ms 66092 KB Output is correct
6 Correct 32 ms 66260 KB Output is correct
7 Correct 32 ms 66120 KB Output is correct
8 Correct 42 ms 66192 KB Output is correct
9 Correct 35 ms 66260 KB Output is correct
10 Correct 34 ms 66004 KB Output is correct
11 Correct 42 ms 68052 KB Output is correct
12 Correct 56 ms 69392 KB Output is correct
13 Correct 79 ms 82336 KB Output is correct
14 Correct 129 ms 77176 KB Output is correct
15 Correct 177 ms 77884 KB Output is correct
16 Correct 120 ms 74904 KB Output is correct
17 Correct 110 ms 74128 KB Output is correct
18 Correct 63 ms 70352 KB Output is correct
19 Correct 164 ms 78788 KB Output is correct
20 Correct 158 ms 79604 KB Output is correct
21 Correct 152 ms 76888 KB Output is correct
22 Correct 141 ms 75692 KB Output is correct
23 Correct 135 ms 79948 KB Output is correct
24 Correct 33 ms 66132 KB Output is correct
25 Correct 48 ms 68384 KB Output is correct
26 Correct 68 ms 70052 KB Output is correct
27 Correct 78 ms 83324 KB Output is correct
28 Correct 155 ms 78872 KB Output is correct
29 Correct 176 ms 79820 KB Output is correct
30 Correct 145 ms 76444 KB Output is correct
31 Correct 115 ms 75676 KB Output is correct
32 Correct 64 ms 70216 KB Output is correct
33 Correct 161 ms 78796 KB Output is correct
34 Correct 161 ms 79880 KB Output is correct
35 Correct 129 ms 76856 KB Output is correct
36 Correct 121 ms 75800 KB Output is correct
37 Correct 162 ms 80076 KB Output is correct
38 Correct 149 ms 92180 KB Output is correct