oj.uz

Submission #580907

# Submission time Handle Problem Language Result Execution time Memory
580907 2022-06-22T05:56:05 Z benson1029 Tropical Garden (IOI11_garden) C++14
49 / 100
 161 ms 150140 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;
		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 39 ms 66260 KB Output is correct
2 Correct 32 ms 66160 KB Output is correct
3 Correct 33 ms 66132 KB Output is correct
4 Correct 38 ms 66072 KB Output is correct
5 Correct 32 ms 65996 KB Output is correct
6 Correct 36 ms 66212 KB Output is correct
7 Correct 31 ms 65996 KB Output is correct
8 Correct 32 ms 66132 KB Output is correct
9 Correct 37 ms 66264 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 66260 KB Output is correct
2 Correct 32 ms 66160 KB Output is correct
3 Correct 33 ms 66132 KB Output is correct
4 Correct 38 ms 66072 KB Output is correct
5 Correct 32 ms 65996 KB Output is correct
6 Correct 36 ms 66212 KB Output is correct
7 Correct 31 ms 65996 KB Output is correct
8 Correct 32 ms 66132 KB Output is correct
9 Correct 37 ms 66264 KB Output is correct
10 Correct 33 ms 66124 KB Output is correct
11 Correct 52 ms 68044 KB Output is correct
12 Correct 58 ms 69340 KB Output is correct
13 Correct 72 ms 82296 KB Output is correct
14 Correct 122 ms 77268 KB Output is correct
15 Correct 143 ms 78004 KB Output is correct
16 Correct 150 ms 74828 KB Output is correct
17 Runtime error 161 ms 150140 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 39 ms 66260 KB Output is correct
2 Correct 32 ms 66160 KB Output is correct
3 Correct 33 ms 66132 KB Output is correct
4 Correct 38 ms 66072 KB Output is correct
5 Correct 32 ms 65996 KB Output is correct
6 Correct 36 ms 66212 KB Output is correct
7 Correct 31 ms 65996 KB Output is correct
8 Correct 32 ms 66132 KB Output is correct
9 Correct 37 ms 66264 KB Output is correct
10 Correct 33 ms 66124 KB Output is correct
11 Correct 52 ms 68044 KB Output is correct
12 Correct 58 ms 69340 KB Output is correct
13 Correct 72 ms 82296 KB Output is correct
14 Correct 122 ms 77268 KB Output is correct
15 Correct 143 ms 78004 KB Output is correct
16 Correct 150 ms 74828 KB Output is correct
17 Runtime error 161 ms 150140 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -