oj.uz

답안 #132964

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132964 2019-07-20T03:01:42 Z Boxworld 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 5000 ms 1656 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN=150100;
struct edge{int v,nxt,pa;}a[maxN];
int k,p,m,tmp=0,ans=0,head[maxN],vis[maxN];
void add(int u,int v,int pa){
	a[tmp].pa=tmp+pa;a[tmp].v=v;a[tmp].nxt=head[u];head[u]=tmp++;
//	printf("Edge#%d u=%d v=%d PairEdge#%d\n",tmp-1,u,a[tmp-1].v,a[tmp-1].pa);
}
void dfs(int u,int ed,int in){
	int P;
	if (in!=-1){
		P=a[in].pa;
		vis[in]=1;
		vis[P]=1;
	//	printf("from:%d to:%d Edge#%d vis_edge:%d\n",a[P].v,u,in,ed);
	}
	if(ed==k){
		if (u==p)ans++;
		return;
	}
	int need_back=1;
	for (int i=head[u];i!=-1;i=a[i].nxt){
		if (i==P)continue;
		dfs(a[i].v,ed+1,i);
		need_back=0;
		return;
	}
	if (need_back)dfs(a[P].v,ed+1,P);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	k=G[0];p=P;m=M;
	for (int i=0;i<N;i++)head[i]=-1;
	for (int i=M-1;i>=0;i--){
		add(R[i][0],R[i][1],1);
		add(R[i][1],R[i][0],-1);
	}
	for (int i=0;i<N;i++){
	//	printf("Start=%d\n",i);
		memset(vis,0,sizeof(vis));
		dfs(i,0,-1);
	}
	answer(ans);
}

Compilation message

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:26:3: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (i==P)continue;
   ^~

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 888 KB Output is correct
2 Correct 33 ms 1016 KB Output is correct
3 Correct 32 ms 1024 KB Output is correct
4 Correct 4 ms 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 35 ms 1048 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 36 ms 1016 KB Output is correct
9 Correct 36 ms 1144 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 888 KB Output is correct
2 Correct 33 ms 1016 KB Output is correct
3 Correct 32 ms 1024 KB Output is correct
4 Correct 4 ms 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 35 ms 1048 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 36 ms 1016 KB Output is correct
9 Correct 36 ms 1144 KB Output is correct
10 Correct 12 ms 888 KB Output is correct
11 Execution timed out 5003 ms 1656 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 888 KB Output is correct
2 Correct 33 ms 1016 KB Output is correct
3 Correct 32 ms 1024 KB Output is correct
4 Correct 4 ms 888 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 35 ms 1048 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 36 ms 1016 KB Output is correct
9 Correct 36 ms 1144 KB Output is correct
10 Correct 12 ms 888 KB Output is correct
11 Execution timed out 5003 ms 1656 KB Time limit exceeded
12 Halted 0 ms 0 KB -