oj.uz

Submission #94655

# Submission time Handle Problem Language Result Execution time Memory
94655 2019-01-22T06:47:43 Z andy627 Tropical Garden (IOI11_garden) C++17
49 / 100
 23 ms 19984 KB 
#include "gardenlib.h"

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;

int n;
vector<int> edge[155555];
vector<int> gph[333333],rev[333333];

int cyc;
int dfn[333333];

int ans1[333333],ans2[333333];
bool is_gone[333333];

void dfs1(int v,int p,int dist){
	if(dfn[v]){
		cyc=dist-dfn[v];
		return;
	}

	dfn[v]=dist;
	for(int u:gph[v]){
		if(u==p) continue;
		dfs1(u,v,dist+1);
	}
}

void dfs2(int v,int p,int dist){
	//printf("%d %d!\n",v,dist);

	is_gone[v]=1;
	if(v%2==0){
		for(int i=dist;i<=(n<<1);i+=cyc) ans1[i]++;
		ans2[dist%cyc]++;
	}

	for(int u:rev[v]){
		if(u==p || is_gone[u]) continue;
		dfs2(u,v,dist+1);
	}
	is_gone[v]=0;
}

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++){
		edge[R[i][0]].push_back(R[i][1]);
		edge[R[i][1]].push_back(R[i][0]);
	}

	for(int i=0;i<N;i++){
		if(edge[i].size()>2) edge[i].resize(2);
		if(edge[i].size()==1) edge[i].push_back(edge[i][0]);

		if(edge[edge[i][0]][0]==i){
			gph[i<<1].push_back(edge[i][0]<<1|1);
			rev[edge[i][0]<<1|1].push_back(i<<1);
		}
		else{
			gph[i<<1].push_back(edge[i][0]<<1);
			rev[edge[i][0]<<1].push_back(i<<1);
		}

		if(edge[edge[i][1]][0]==i){
			gph[i<<1|1].push_back(edge[i][1]<<1|1);
			rev[edge[i][1]<<1|1].push_back(i<<1|1);
		}
		else{
			gph[i<<1|1].push_back(edge[i][1]<<1);
			rev[edge[i][1]<<1].push_back(i<<1|1);
		}
	}

	//for(int i=0;i<(N<<1);i++){
	//	printf("#%d : ",i); 
	//	for(int j:rev[i]) printf("%d ",j);
	//	printf("\n");
	//}


	dfs1(0,0,1);
	//printf("cyc%d\n",cyc);
	dfs2(P<<1,P<<1,0);
	dfs2(P<<1|1,P<<1|1,0);

	//for(int i=0;i<(N<<1);i++) printf("%d ",ans1[i]); printf("\n");
	//for(int i=0;i<cyc;i++) printf("%d ",ans2[i]); printf("\n");
	//printf("%d\n",cyc);

	//for(int i=0;i<(N<<1);i++) printf("%d ",ans1[i]); printf("\n");
	//for(int i=0;i<cyc;i++) printf("%d ",ans2[i]); printf("\n");

	for(int i=0;i<Q;i++){
		if(G[i]>(N<<1)) answer(ans2[G[i]%cyc]);
		else answer(ans1[G[i]]);
	}

	return;
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19896 KB Output is correct
2 Correct 20 ms 19832 KB Output is correct
3 Correct 21 ms 19896 KB Output is correct
4 Correct 20 ms 19608 KB Output is correct
5 Correct 20 ms 19676 KB Output is correct
6 Correct 21 ms 19984 KB Output is correct
7 Correct 19 ms 19660 KB Output is correct
8 Correct 21 ms 19744 KB Output is correct
9 Correct 23 ms 19984 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19896 KB Output is correct
2 Correct 20 ms 19832 KB Output is correct
3 Correct 21 ms 19896 KB Output is correct
4 Correct 20 ms 19608 KB Output is correct
5 Correct 20 ms 19676 KB Output is correct
6 Correct 21 ms 19984 KB Output is correct
7 Correct 19 ms 19660 KB Output is correct
8 Correct 21 ms 19744 KB Output is correct
9 Correct 23 ms 19984 KB Output is correct
10 Incorrect 19 ms 19664 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19896 KB Output is correct
2 Correct 20 ms 19832 KB Output is correct
3 Correct 21 ms 19896 KB Output is correct
4 Correct 20 ms 19608 KB Output is correct
5 Correct 20 ms 19676 KB Output is correct
6 Correct 21 ms 19984 KB Output is correct
7 Correct 19 ms 19660 KB Output is correct
8 Correct 21 ms 19744 KB Output is correct
9 Correct 23 ms 19984 KB Output is correct
10 Incorrect 19 ms 19664 KB Output isn't correct
11 Halted 0 ms 0 KB -