oj.uz

Submission #116575

# Submission time Handle Problem Language Result Execution time Memory
116575 2019-06-13T00:41:49 Z andremfq Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1615 ms 66360 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];
int n1;
void dfs1(int v)
{
	set<pair<pair<int,int>,int > > s;
	for(int i=0;i<n1;i++)
	{
		if(d1[i]==0)s.insert(make_pair(make_pair(d2[i],d1[i]),i));
	}
	while(!s.empty())
	{
		int cur=s.begin()->second;
		s.erase(make_pair(make_pair(d2[cur],d1[cur]),cur));
		for(int i=0;i<grf[cur].size();i++)
		{
			int viz=grf[cur][i],p=ps[cur][i];
			if(d2[viz]<=d2[cur]+p)continue;
			s.erase(make_pair(make_pair(d2[viz],d1[viz]),viz));
			d2[viz]=min(d2[viz],d2[cur]+p);
			if(d2[viz]<d1[viz])swap(d2[viz],d1[viz]);
			s.insert(make_pair(make_pair(d2[viz],d1[viz]),viz));
		}
	}
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
	n1=n;
	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;
	}
	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:20:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grf[cur].size();i++)
               ~^~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 5 ms 4992 KB Output is correct
11 Correct 8 ms 5160 KB Output is correct
12 Correct 10 ms 5504 KB Output is correct
13 Correct 9 ms 5504 KB Output is correct
14 Correct 6 ms 5120 KB Output is correct
15 Correct 7 ms 5116 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 5 ms 4992 KB Output is correct
11 Correct 8 ms 5160 KB Output is correct
12 Correct 10 ms 5504 KB Output is correct
13 Correct 9 ms 5504 KB Output is correct
14 Correct 6 ms 5120 KB Output is correct
15 Correct 7 ms 5116 KB Output is correct
16 Correct 981 ms 59100 KB Output is correct
17 Correct 110 ms 17764 KB Output is correct
18 Correct 185 ms 19752 KB Output is correct
19 Correct 1615 ms 66360 KB Output is correct
20 Correct 437 ms 52760 KB Output is correct
21 Correct 61 ms 10488 KB Output is correct
22 Correct 374 ms 49000 KB Output is correct