oj.uz

Submission #580904

# Submission time Handle Problem Language Result Execution time Memory
580904 2022-06-22T05:53:27 Z benson1029 Tropical Garden (IOI11_garden) C++14
49 / 100
 178 ms 75400 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;

vector< int > edg[300005];

int n;
int nxt[300005];
vector<int> p[300005];
bool vis1[300005], vis2[300005];
int dis1[300005], dis2[300005];
vector<int> ans1[300005], ans2[300005];
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<=2*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;
		ans += upper_bound(ans1[g%mod1].begin(), ans1[g%mod1].end(), g) - ans1[g%mod1].begin();
		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 15 ms 28636 KB Output is correct
2 Correct 18 ms 28628 KB Output is correct
3 Correct 17 ms 28628 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 18 ms 28456 KB Output is correct
6 Correct 18 ms 28768 KB Output is correct
7 Correct 20 ms 28432 KB Output is correct
8 Correct 16 ms 28660 KB Output is correct
9 Correct 19 ms 28808 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28636 KB Output is correct
2 Correct 18 ms 28628 KB Output is correct
3 Correct 17 ms 28628 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 18 ms 28456 KB Output is correct
6 Correct 18 ms 28768 KB Output is correct
7 Correct 20 ms 28432 KB Output is correct
8 Correct 16 ms 28660 KB Output is correct
9 Correct 19 ms 28808 KB Output is correct
10 Correct 15 ms 28500 KB Output is correct
11 Correct 27 ms 30752 KB Output is correct
12 Correct 44 ms 32408 KB Output is correct
13 Correct 94 ms 45772 KB Output is correct
14 Correct 140 ms 41276 KB Output is correct
15 Correct 178 ms 42076 KB Output is correct
16 Correct 135 ms 38796 KB Output is correct
17 Runtime error 154 ms 75400 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28636 KB Output is correct
2 Correct 18 ms 28628 KB Output is correct
3 Correct 17 ms 28628 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 18 ms 28456 KB Output is correct
6 Correct 18 ms 28768 KB Output is correct
7 Correct 20 ms 28432 KB Output is correct
8 Correct 16 ms 28660 KB Output is correct
9 Correct 19 ms 28808 KB Output is correct
10 Correct 15 ms 28500 KB Output is correct
11 Correct 27 ms 30752 KB Output is correct
12 Correct 44 ms 32408 KB Output is correct
13 Correct 94 ms 45772 KB Output is correct
14 Correct 140 ms 41276 KB Output is correct
15 Correct 178 ms 42076 KB Output is correct
16 Correct 135 ms 38796 KB Output is correct
17 Runtime error 154 ms 75400 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -