oj.uz

Submission #834138

# Submission time Handle Problem Language Result Execution time Memory
834138 2023-08-22T11:04:56 Z ttamx Tropical Garden (IOI11_garden) C++14
100 / 100
 2280 ms 37880 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>

using namespace std;

const int N=150005;
const int M=300005;
const int inf=2e9;

int n,p;
vector<int> padj[N];
vector<pair<int,int>> adj[N][2];
int dp[2][N][2];
int cyc[2];

void dfs(int t,int u,int s,int d=0){
	dp[t][u][s]=d;
	for(auto [v,w]:adj[u][s]){
		if(v==p&&w==t){
			cyc[t]=d+1;
		}else{
			dfs(t,v,w,d+1);
		}
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n=N,p=P;
	for(int t=0;t<2;t++)for(int i=0;i<n;i++)dp[t][i][0]=dp[t][i][1]=inf;
	for(int i=0;i<M;i++){
		int u=R[i][0],v=R[i][1];
		padj[u].emplace_back(v);
		padj[v].emplace_back(u);
	}
	for(int u=0;u<n;u++){
		for(int s=0;s<2;s++){
			int v=padj[u][min(s,(int)padj[u].size()-1)];
			adj[v][padj[v][0]==u].emplace_back(u,s);
		}
	}
	dfs(0,p,0);
	dfs(1,p,1);
	for(int i=0;i<Q;i++){
		int k=G[i];
		int ans=0;
		for(int u=0;u<n;u++){
			bool ok=false;
			for(int t=0;t<2;t++){
				if(dp[t][u][0]>k)continue;
				int d=k-dp[t][u][0];
				if(cyc[t])d%=cyc[t];
				ok|=d==0;
			}
			ans+=ok;
		}
		answer(ans);
	}
}

Compilation message

garden.cpp: In function 'void dfs(int, int, int, int)':
garden.cpp:19:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |  for(auto [v,w]:adj[u][s]){
      |           ^

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10964 KB Output is correct
2 Correct 5 ms 10964 KB Output is correct
3 Correct 5 ms 10964 KB Output is correct
4 Correct 5 ms 10836 KB Output is correct
5 Correct 5 ms 10836 KB Output is correct
6 Correct 5 ms 11040 KB Output is correct
7 Correct 5 ms 10836 KB Output is correct
8 Correct 5 ms 10964 KB Output is correct
9 Correct 8 ms 11092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10964 KB Output is correct
2 Correct 5 ms 10964 KB Output is correct
3 Correct 5 ms 10964 KB Output is correct
4 Correct 5 ms 10836 KB Output is correct
5 Correct 5 ms 10836 KB Output is correct
6 Correct 5 ms 11040 KB Output is correct
7 Correct 5 ms 10836 KB Output is correct
8 Correct 5 ms 10964 KB Output is correct
9 Correct 8 ms 11092 KB Output is correct
10 Correct 5 ms 10836 KB Output is correct
11 Correct 12 ms 13148 KB Output is correct
12 Correct 23 ms 14708 KB Output is correct
13 Correct 47 ms 31528 KB Output is correct
14 Correct 97 ms 23740 KB Output is correct
15 Correct 102 ms 24052 KB Output is correct
16 Correct 71 ms 20440 KB Output is correct
17 Correct 70 ms 19196 KB Output is correct
18 Correct 23 ms 14716 KB Output is correct
19 Correct 83 ms 23684 KB Output is correct
20 Correct 118 ms 23884 KB Output is correct
21 Correct 82 ms 20368 KB Output is correct
22 Correct 69 ms 19024 KB Output is correct
23 Correct 109 ms 24984 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10964 KB Output is correct
2 Correct 5 ms 10964 KB Output is correct
3 Correct 5 ms 10964 KB Output is correct
4 Correct 5 ms 10836 KB Output is correct
5 Correct 5 ms 10836 KB Output is correct
6 Correct 5 ms 11040 KB Output is correct
7 Correct 5 ms 10836 KB Output is correct
8 Correct 5 ms 10964 KB Output is correct
9 Correct 8 ms 11092 KB Output is correct
10 Correct 5 ms 10836 KB Output is correct
11 Correct 12 ms 13148 KB Output is correct
12 Correct 23 ms 14708 KB Output is correct
13 Correct 47 ms 31528 KB Output is correct
14 Correct 97 ms 23740 KB Output is correct
15 Correct 102 ms 24052 KB Output is correct
16 Correct 71 ms 20440 KB Output is correct
17 Correct 70 ms 19196 KB Output is correct
18 Correct 23 ms 14716 KB Output is correct
19 Correct 83 ms 23684 KB Output is correct
20 Correct 118 ms 23884 KB Output is correct
21 Correct 82 ms 20368 KB Output is correct
22 Correct 69 ms 19024 KB Output is correct
23 Correct 109 ms 24984 KB Output is correct
24 Correct 6 ms 10836 KB Output is correct
25 Correct 80 ms 13256 KB Output is correct
26 Correct 119 ms 14708 KB Output is correct
27 Correct 2054 ms 31544 KB Output is correct
28 Correct 745 ms 23792 KB Output is correct
29 Correct 2242 ms 23884 KB Output is correct
30 Correct 1324 ms 20472 KB Output is correct
31 Correct 1279 ms 19152 KB Output is correct
32 Correct 130 ms 14716 KB Output is correct
33 Correct 762 ms 23748 KB Output is correct
34 Correct 2280 ms 23976 KB Output is correct
35 Correct 1401 ms 20348 KB Output is correct
36 Correct 1292 ms 19148 KB Output is correct
37 Correct 636 ms 25036 KB Output is correct
38 Correct 1815 ms 37880 KB Output is correct