oj.uz

Submission #580890

# Submission time Handle Problem Language Result Execution time Memory
580890 2022-06-22T05:24:20 Z benson1029 Tropical Garden (IOI11_garden) C++14
0 / 100
 15 ms 28640 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<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
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28628 KB Output is correct
2 Incorrect 15 ms 28640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28628 KB Output is correct
2 Incorrect 15 ms 28640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28628 KB Output is correct
2 Incorrect 15 ms 28640 KB Output isn't correct
3 Halted 0 ms 0 KB -