답안 #49992 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49992	2018-06-06T04:19:02 Z	Diuven	열대 식물원 (Tropical Garden) (IOI11_garden)	C++11	100 / 100	4914 ms	14192 KB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=300010, inf=2e9;

int n, nxt[MX], Q1, Q2; // in, out

void debug(){
	for(int i=0; i<n; i++)
		cout<<nxt[i]<<' ';
	cout<<"\n\n";
}


int fir[MX], scd[MX];
void init(int V, int E, int P, int R[][2]){
	fill(fir, fir+n, -1);
	fill(scd, scd+n, -1);
	// u->v: 0, v->u: 1
	for(int i=0; i<E; i++){
		int u=R[i][0], v=R[i][1];
		if(fir[u]<0) fir[u]=2*i;
		else if(scd[u]<0) scd[u]=2*i;
		if(fir[v]<0) fir[v]=2*i+1;
		else if(scd[v]<0) scd[v]=2*i+1;
	}
	for(int i=0; i<E; i++){
		int u=R[i][0], v=R[i][1];
		// u->v, v->u
		if(fir[v]==2*i+1 && scd[v]>=0) nxt[2*i]=scd[v];
		else nxt[2*i]=fir[v];
		if(fir[u]==2*i && scd[u]>=0) nxt[2*i+1]=scd[u];
		else nxt[2*i+1]=fir[u];
	}
	Q1=fir[P]+(fir[P]%2==0 ? 1 : -1), Q2=fir[P];
}

int D1[MX], D2[MX], cyc1, cyc2;

bool vis1[MX], vis2[MX], vis3[MX];

int dep[MX], now;

void dfs1(int v){
	vis1[v]=true; dep[v]=++now;
	if(v==Q1) D1[v]=0;
	int x=nxt[v];
	if(!vis1[x]) dfs1(x);
	if(x==Q1) cyc1=dep[v]-dep[x]+1;
	D1[v]=min(D1[v], D1[x]+1);
}
void dfs2(int v){
	vis2[v]=true; dep[v]=++now;
	if(v==Q2) D2[v]=0;
	int x=nxt[v];
	if(!vis2[x]) dfs2(x);
	if(x==Q2) cyc2=dep[v]-dep[x]+1;
	D2[v]=min(D2[v], D2[x]+1);
}

void dfs3(int v){
	vis3[v]=true;
	int x=nxt[v];
	if(!vis3[x]) dfs3(x);
	D1[v]=min(D1[v], (D1[x]==inf ? inf : D1[x]+1)); 
	D2[v]=min(D2[v], (D2[x]==inf ? inf : D2[x]+1)); 
}

void prec(){
	fill(D1, D1+n, inf); D1[Q1]=0;
	fill(D2, D2+n, inf); D2[Q2]=0;
	cyc1=cyc2=0;
	dfs1(Q1);
	dfs2(Q2);
	for(int i=0; i<n; i++)
		vis3[i]=vis1[i]&&vis2[i];
	for(int i=0; i<n; i++){
		if(vis3[i]) continue;
		dfs3(i);
	}
}

bool valid(int d, int k, int c){
	if(d>=inf/2) return false;
	return (c==0 && k==d) || (c!=0 && d<=k && (k-d)%c==0);
}

int solve(int k, int V){
	int ans=0;
	for(int i=0; i<V; i++){
		int e=fir[i];
		ans+=(valid(D1[e]+1, k, cyc1) || valid(D2[e], k, cyc2));
	}
	return ans;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n=2*M;

	init(N,M,P,R);
	prec();

	for(int i=0; i<Q; i++)
		answer(solve(G[i], N));
}

Subtask #1
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	1 ms	476 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	504 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	2 ms	372 KB	Output is correct
9	Correct	4 ms	828 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	1 ms	476 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	504 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	2 ms	372 KB	Output is correct
9	Correct	4 ms	828 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	9 ms	1784 KB	Output is correct
12	Correct	20 ms	3396 KB	Output is correct
13	Correct	37 ms	10956 KB	Output is correct
14	Correct	53 ms	7496 KB	Output is correct
15	Correct	55 ms	7612 KB	Output is correct
16	Correct	51 ms	7212 KB	Output is correct
17	Correct	51 ms	7132 KB	Output is correct
18	Correct	20 ms	3192 KB	Output is correct
19	Correct	52 ms	7288 KB	Output is correct
20	Correct	55 ms	7616 KB	Output is correct
21	Correct	52 ms	7432 KB	Output is correct
22	Correct	54 ms	7152 KB	Output is correct
23	Correct	54 ms	7800 KB	Output is correct

Subtask #3
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	1 ms	476 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	3 ms	504 KB	Output is correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	2 ms	372 KB	Output is correct
9	Correct	4 ms	828 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	9 ms	1784 KB	Output is correct
12	Correct	20 ms	3396 KB	Output is correct
13	Correct	37 ms	10956 KB	Output is correct
14	Correct	53 ms	7496 KB	Output is correct
15	Correct	55 ms	7612 KB	Output is correct
16	Correct	51 ms	7212 KB	Output is correct
17	Correct	51 ms	7132 KB	Output is correct
18	Correct	20 ms	3192 KB	Output is correct
19	Correct	52 ms	7288 KB	Output is correct
20	Correct	55 ms	7616 KB	Output is correct
21	Correct	52 ms	7432 KB	Output is correct
22	Correct	54 ms	7152 KB	Output is correct
23	Correct	54 ms	7800 KB	Output is correct
24	Correct	3 ms	376 KB	Output is correct
25	Correct	100 ms	1948 KB	Output is correct
26	Correct	131 ms	3680 KB	Output is correct
27	Correct	1797 ms	11432 KB	Output is correct
28	Correct	1219 ms	8032 KB	Output is correct
29	Correct	1950 ms	8332 KB	Output is correct
30	Correct	1199 ms	7940 KB	Output is correct
31	Correct	1138 ms	7868 KB	Output is correct
32	Correct	178 ms	3576 KB	Output is correct
33	Correct	1249 ms	8032 KB	Output is correct
34	Correct	1832 ms	8336 KB	Output is correct
35	Correct	1236 ms	8024 KB	Output is correct
36	Correct	2192 ms	7936 KB	Output is correct
37	Correct	885 ms	8548 KB	Output is correct
38	Correct	4914 ms	14192 KB	Output is correct

답안 #49992

Compilation message

Subtask #1 49.0 / 49.0

Subtask #2 20.0 / 20.0

Subtask #3 31.0 / 31.0

Subtask #1
49.0 / 49.0

Subtask #2
20.0 / 20.0

Subtask #3
31.0 / 31.0