Submission #118873

#	Time	Username	Problem	Language	Result	Execution time	Memory
118873		CaroLinda	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	898 ms	68348 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"

#define pb push_back
#define lp(i,a,b) for(int i=a;i<b;i++)
#define ff first
#define ss second
#define pii pair<int,int>
#define mk make_pair

const int maxn=1e5+10 ;
const int maxm=1e6+10 ;
const int inf=1e9+10;

using namespace std;

// ----------- x -----------

struct ansVertex
{
	pii best, secondBest ;
	
	ansVertex()
	{ best=secondBest=pii(inf,-1) ; }
	
	void update(pii p)
	{
		if(best.ff == inf ) { best = p; return ; }
		if(best.ff>p.ff)
		{
			if(best.ss != p.ss) secondBest=best;
			best=p;
			return;
		}
		if(secondBest.ff>p.ff && best.ss != p.ss) secondBest=p ;
	}
	
};

// ----------- x -----------

int n,m,k;
int p[maxn] ;
vector<pii> adj[maxn];
bool marc[maxn] ;

int dijkstra()
{
	priority_queue<pii> myQueue ;
	ansVertex v[maxn];
	
	lp(i,0,k) 
	{
		myQueue.push(pii(0,p[i])) ;
		v[p[i]].best = v[p[i]].secondBest=pii(0,p[i]) ;
	}
	
	while(true)
	{
		int forNow=-1;
		while(!myQueue.empty() )
		{
			pii t = myQueue.top() ;
			myQueue.pop();
			if(!marc[t.ss])
			{
				forNow=t.ss ;
				marc[forNow]=true ;
				break ;
			}
		}
		if(forNow==-1)break;

		lp(i,0,adj[forNow].size())
		{
			pii littleV = adj[forNow][i] ;
			v[littleV.ff].update(pii(v[forNow].secondBest.ff + littleV.ss, forNow )) ;
			if(v[littleV.ff].secondBest.ff!=-1 && !marc[littleV.ff])
			myQueue.push( pii( -v[littleV.ff].secondBest.ff, littleV.ff ) ) ;
		}
	}
	return v[0].secondBest.ff ;
}

int travel_plan(int N,int M,int R[][2],int L[],int K,int P[])
{
	n=N;m=M;k=K;
	lp(i,0,m)
	{
		int a=R[i][0],b=R[i][1];
		adj[a].pb(pii(b,L[i]));
		adj[b].pb(pii(a,L[i])) ;
	}
	lp(i,0,K)p[i]=P[i];
	return dijkstra() ;
}

Compilation message (stderr)

crocodile.cpp: In function 'int dijkstra()':
crocodile.cpp:5:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
crocodile.cpp:74:6:
   lp(i,0,adj[forNow].size())
      ~~~~~~~~~~~~~~~~~~~~~~     
crocodile.cpp:74:3: note: in expansion of macro 'lp'
   lp(i,0,adj[forNow].size())
   ^~

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11