oj.uz

Submission #133007

# Submission time Handle Problem Language Result Execution time Memory
133007 2019-07-20T04:10:53 Z StevenH Tropical Garden (IOI11_garden) C++14
49 / 100
 5000 ms 988 KB 
#include "garden.h"
#include "gardenlib.h"
#include <iostream>
using namespace std;
const int maxn = 1005;
const int maxm = 100005;
struct Edge{
	int to,dis,next;
}edge[maxm*2];
int head[maxn],edge_num;
void addedge(int from,int to,int dis)
{
	edge[++edge_num].to=to;
	edge[edge_num].dis=dis;
	edge[edge_num].next=head[from];
	head[from]=edge_num;
}
int p;
int f[maxn];
int dfs(int x,int last,int step)
{
	//cout<<x<<" ";
	if(p==step)
	{
		return x;
	}
	int res=9999999;
	int minv=-1;
	for(int i=head[x];i;i=edge[i].next)
	{
		int v=edge[i].to;
		int dist=edge[i].dis;
		if(!edge[i].next && i==head[x])res=dist,minv=v;
		else if(dist<res && v!=last)res=dist,minv=v;
	}
	p++;
	return dfs(minv,x,step);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	int i;
	for(int i=0;i<M;i++)
	{
		addedge(R[i][0],R[i][1],i);
		addedge(R[i][1],R[i][0],i);	
	}	
	for(i=0; i<Q; i++)
	{
		int cnt=0;
		for(int j=0;j<N;j++)
		{
			p=0;
			if(dfs(j,-1,G[i])==P)cnt++;
		}
		answer(cnt);
	}	
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 14 ms 632 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 14 ms 632 KB Output is correct
10 Correct 16 ms 420 KB Output is correct
11 Execution timed out 5047 ms 988 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 14 ms 632 KB Output is correct
10 Correct 16 ms 420 KB Output is correct
11 Execution timed out 5047 ms 988 KB Time limit exceeded
12 Halted 0 ms 0 KB -