Submission #116575

#	Time	Username	Problem	Language	Result	Execution time	Memory
116575		andremfq	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1615 ms	66360 KiB

crocodile

#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 (stderr)

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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11