Submission #132951

#	Time	Username	Problem	Language	Result	Execution time	Memory
132951		Boxworld	Tropical Garden (IOI11_garden)	C++14	0 / 100	28 ms	1016 KiB

garden

#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,tmp=0,ans=0,head[maxN],vis[maxN];
void add(int u,int v,int pa){
	a[tmp].pa=pa;a[tmp].v=v;a[tmp].nxt=head[u];head[u]=tmp++;
}
void dfs(int u,int ed,int in){
	if (in!=-1)vis[in]=1,vis[in+a[in].pa]=1;
	if(ed==k){
		if (u==p)ans++;
		return;
	}
	int need_back=1;
	for (int i=head[u];i!=-1;i=a[i].nxt){
		if (vis[i])continue;
		dfs(a[i].v,ed+1,i);
		need_back=0;
		break;
	}
	if (need_back)dfs(a[in+a[in].pa].v,ed+1,in+a[in].pa);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	k=G[0];p=P;
	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++){
		memset(vis,0,sizeof(vis));
		dfs(i,0,-1);
	}
	answer(ans);
}

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31