oj.uz

Submission #294275

# Submission time Handle Problem Language Result Execution time Memory
294275 2020-09-08T18:49:19 Z crackersamdjam Tropical Garden (IOI11_garden) C++17
100 / 100
 4326 ms 17288 KB 
#define OJUZ

#ifdef OJUZ
#include "garden.h"
#include "gardenlib.h"
#define ONLINE_JUDGE
#endif

#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#endif

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar()
#define pc(x) putchar(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=char(n%10+48);n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

#define f first
#define s second

using namespace std;
using pii = pair<int, int>;
const int MM = 150005, TWO = 1e8, inf = 1e9;

int n, m, p, k;
vector<pii> in[MM];
pii nx[MM][2];
int dis[MM][2], f[MM], s[MM], len, id, cnt[MM], cnta[MM], cntb[MM];
bool vis[MM][2];
//0 = go to best next one
//1 = go to second best one

#ifndef ONLINE_JUDGE
void answer(int X){
	print(X);
}
#endif

void go(int cur, bool f, int d){
	vis[cur][f] = 1;
	int u, w;
	tie(u, w) = nx[cur][f];
	if(u == p){
		len = d+1;
		id = w;
		return;
	}
	if(!vis[u][w])
		go(u, w, d+1);
}

int dfs(int cur, bool f){
	if(~dis[cur][f])
		return dis[cur][f];
	dis[cur][f] = inf;
	return dis[cur][f] = dfs(nx[cur][f].first, nx[cur][f].second)+1;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n = N, m = M, p = P, k = Q;
	for(int i = 0; i < m; i++){
		in[R[i][0]].emplace_back(i, R[i][1]);
		in[R[i][1]].emplace_back(i, R[i][0]);
	}
	for(int i = 0; i < n; i++){
		sort(all(in[i]));
		// assert(size(in[i]));
		if(size(in[i]) == 1)
			in[i].emplace_back(in[i][0]);
		else
			in[i].resize(2);
	}
	for(int i = 0,u,w; i < n; i++){
		tie(w, u) = in[i][0];
		nx[i][0] = {u, (w == in[u][0].first)};
		tie(w, u) = in[i][1];
		nx[i][1] = {u, (w == in[u][0].first)};
	}
	//find "final" cycle distances
	memset(vis, 0, sizeof vis);
	len = inf, id = -1;
	go(p, 0, 0);
	int lena = len, ida = id;

	memset(vis, 0, sizeof vis);
	len = inf, id = -1;
	go(p, 1, 0);
	int lenb = len, idb = id;

	// either no cycle, 0/1 itself cycle, lead into other cycle, or large cycle with both...

	int moda, offa, modb, offb;
	if(ida == -1){
		moda = inf;
		offa = inf;
	}
	else if(ida == 0){
		moda = lena;
		offa = 0;
	}
	else{
		moda = lenb;
		offa = lena;
	}

	if(idb == -1){
		modb = inf;
		offb = inf;
	}
	else if(idb == 1){
		modb = lenb;
		offb = 0;
	}
	else{
		modb = lena;
		offb = lenb;
	}
	int mod2 = (moda+modb);

	if(ida == 1 and idb == 0){
		//large cycle with both
		// abort();
	}

	memset(dis, -1, sizeof dis);
	dis[p][0] =  0;
	dis[p][1] = TWO; //to tell apart
	
	for(int i = 0; i < N; i++){
		dfs(i, 0);
	}

	for(int i = 0; i < Q; i++){
		int v = G[i], ans = 0;
		for(int j = 0; j < n; j++){
			// int l = dfs(j, 0);
			int l = dis[j][0];
			if(l >= inf or l == -1) continue;

			//large cycle with both
			if(ida == 1 and idb == 0){
				if(l >= TWO){
					l -= TWO;
					if(l <= v){
						l %= mod2;
						v %= mod2;
						if(l == v or (l+offb)%mod2 == v)
							ans++;
					}
				}
				else{
					if(l <= v){
						l %= mod2;
						v %= mod2;
						if(l == v or (l+offa)%mod2 == v)
							ans++;
					}
				}
				continue;
			}
			
			if(l >= TWO){
				l -= TWO;
				//second cycle
				if(l == v or (l+offb <= v and (l+offb)%modb == v%modb))
					ans++;
			}
			else{
				if(l == v or (l+offa <= v and (l+offa)%moda == v%moda))
					ans++;
			}
		}
		answer(ans);
	}
}

#ifndef ONLINE_JUDGE
int main(){
	int N, M, P;
	scan(N, M, P);
	int R[M][2];
	for(int i = 0; i < M; i++){
		scan(R[i][0], R[i][1]);
		// print(R[i][0], R[i][1], i);
	}
	int Q;
	scan(Q);
	int G[Q];
	for(int i = 0; i < Q; i++)
		scan(G[i]);
	count_routes(N, M, P, R, Q, G);

	if(0){
		int G[] = {3};
		int R[][2] = {{1, 2}, {0, 1}, {0, 3}, {3, 4}, {4, 5}, {1, 5}};
		count_routes(6, 6, 0, R, 1, G);
	}
	if(0){
		int G[] = {3, 1};
		int R[][2] = {{1, 0}, {1, 2}, {3, 2}, {1, 3}, {4, 2}};
		count_routes(5, 5, 2, R, 2, G);
	}
}
#endif

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5376 KB Output is correct
2 Correct 4 ms 5376 KB Output is correct
3 Correct 4 ms 5376 KB Output is correct
4 Correct 4 ms 5376 KB Output is correct
5 Correct 4 ms 5376 KB Output is correct
6 Correct 5 ms 5504 KB Output is correct
7 Correct 4 ms 5376 KB Output is correct
8 Correct 4 ms 5376 KB Output is correct
9 Correct 9 ms 5760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5376 KB Output is correct
2 Correct 4 ms 5376 KB Output is correct
3 Correct 4 ms 5376 KB Output is correct
4 Correct 4 ms 5376 KB Output is correct
5 Correct 4 ms 5376 KB Output is correct
6 Correct 5 ms 5504 KB Output is correct
7 Correct 4 ms 5376 KB Output is correct
8 Correct 4 ms 5376 KB Output is correct
9 Correct 9 ms 5760 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 14 ms 7040 KB Output is correct
12 Correct 29 ms 8824 KB Output is correct
13 Correct 38 ms 11000 KB Output is correct
14 Correct 112 ms 15480 KB Output is correct
15 Correct 97 ms 15864 KB Output is correct
16 Correct 87 ms 14200 KB Output is correct
17 Correct 82 ms 13688 KB Output is correct
18 Correct 29 ms 8824 KB Output is correct
19 Correct 92 ms 15480 KB Output is correct
20 Correct 111 ms 16000 KB Output is correct
21 Correct 84 ms 14072 KB Output is correct
22 Correct 79 ms 13560 KB Output is correct
23 Correct 93 ms 16376 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5376 KB Output is correct
2 Correct 4 ms 5376 KB Output is correct
3 Correct 4 ms 5376 KB Output is correct
4 Correct 4 ms 5376 KB Output is correct
5 Correct 4 ms 5376 KB Output is correct
6 Correct 5 ms 5504 KB Output is correct
7 Correct 4 ms 5376 KB Output is correct
8 Correct 4 ms 5376 KB Output is correct
9 Correct 9 ms 5760 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 14 ms 7040 KB Output is correct
12 Correct 29 ms 8824 KB Output is correct
13 Correct 38 ms 11000 KB Output is correct
14 Correct 112 ms 15480 KB Output is correct
15 Correct 97 ms 15864 KB Output is correct
16 Correct 87 ms 14200 KB Output is correct
17 Correct 82 ms 13688 KB Output is correct
18 Correct 29 ms 8824 KB Output is correct
19 Correct 92 ms 15480 KB Output is correct
20 Correct 111 ms 16000 KB Output is correct
21 Correct 84 ms 14072 KB Output is correct
22 Correct 79 ms 13560 KB Output is correct
23 Correct 93 ms 16376 KB Output is correct
24 Correct 5 ms 5376 KB Output is correct
25 Correct 92 ms 7040 KB Output is correct
26 Correct 101 ms 8832 KB Output is correct
27 Correct 2131 ms 11132 KB Output is correct
28 Correct 969 ms 15608 KB Output is correct
29 Correct 4285 ms 16064 KB Output is correct
30 Correct 2555 ms 14440 KB Output is correct
31 Correct 2442 ms 13816 KB Output is correct
32 Correct 101 ms 8696 KB Output is correct
33 Correct 971 ms 15724 KB Output is correct
34 Correct 4326 ms 16120 KB Output is correct
35 Correct 2685 ms 14072 KB Output is correct
36 Correct 2435 ms 13564 KB Output is correct
37 Correct 637 ms 16632 KB Output is correct
38 Correct 3814 ms 17288 KB Output is correct