oj.uz

Submission #116572

# Submission time Handle Problem Language Result Execution time Memory
116572 2019-06-13T00:26:37 Z andremfq Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 7 ms 5248 KB 
#include<bits/stdc++.h>
#define debug(args...) //fprintf(stderr,args)
#include "crocodile.h"
using namespace std;
const int MAXN=100010,INF=2123456789;
vector<int> grf[MAXN],ps[MAXN];
int d1[MAXN],d2[MAXN],marc[MAXN];
void dfs1(int v)
{
	debug("at=%d\n",v);
	if(d1[v]==0)return;
	for(int i=0;i<grf[v].size();i++)
	{
		int viz=grf[v][i],p=ps[v][i];
		if(marc[viz]==0)
		{
			marc[viz]=1;
			dfs1(viz);
		}
		marc[viz]=1;
		if(d1[viz]==0)marc[viz]=0;
		d2[v]=min(d2[viz]+p,d2[v]);
		if(d2[v]<d1[v])swap(d1[v],d2[v]);	
	}
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
	for(int i=0;i<m;i++)
	{
		int a=r[i][0],b=r[i][1],pe=l[i];
		grf[a].push_back(b);grf[b].push_back(a);
		ps[a].push_back(pe);ps[b].push_back(pe);
	}
	for(int i=0;i<n;i++)
	{
		d1[i]=INF;d2[i]=INF;
	}
	for(int i=0;i<k;i++)
	{
		d1[p[i]]=0;d2[p[i]]=0;
	}
	marc[0]=1;
	dfs1(0);
	for(int i=0;i<n;i++)
	{
		debug("dist= %d %d\n",d1[i],d2[i]);
	}
	int resp=d2[0];
	if(resp>=INF)resp=-1;
	return resp;
}
/*int r[MAXN][2],l[MAXN],p[MAXN];
int main()
{
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=0;i<m;i++)
	{
		int a,b,P;
		scanf("%d %d %d",&a,&b,&P);
		r[i][0]=a;r[i][1]=b;l[i]=P;
	}
	for(int i=0;i<k;i++)
	{
		scanf("%d",&p[i]);
	}
	printf("%d\n",travel_plan(n,m,r,l,k,p));
	return 0;
}*/

Compilation message

crocodile.cpp: In function 'void dfs1(int)':
crocodile.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<grf[v].size();i++)
              ~^~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 5 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 5 ms 5120 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 5 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 5 ms 5120 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Incorrect 6 ms 5120 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 5 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 5 ms 5120 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Incorrect 6 ms 5120 KB Output isn't correct
11 Halted 0 ms 0 KB -