oj.uz

Submission #118873

# Submission time Handle Problem Language Result Execution time Memory
118873 2019-06-20T00:19:45 Z CaroLinda Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 898 ms 68348 KB 
#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

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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB Output is correct
2 Correct 4 ms 4224 KB Output is correct
3 Correct 6 ms 4224 KB Output is correct
4 Correct 6 ms 4352 KB Output is correct
5 Correct 6 ms 4352 KB Output is correct
6 Correct 6 ms 4288 KB Output is correct
7 Correct 6 ms 4352 KB Output is correct
8 Correct 6 ms 4272 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB Output is correct
2 Correct 4 ms 4224 KB Output is correct
3 Correct 6 ms 4224 KB Output is correct
4 Correct 6 ms 4352 KB Output is correct
5 Correct 6 ms 4352 KB Output is correct
6 Correct 6 ms 4288 KB Output is correct
7 Correct 6 ms 4352 KB Output is correct
8 Correct 6 ms 4272 KB Output is correct
9 Correct 8 ms 4608 KB Output is correct
10 Correct 5 ms 4224 KB Output is correct
11 Correct 6 ms 4352 KB Output is correct
12 Correct 10 ms 4780 KB Output is correct
13 Correct 10 ms 4860 KB Output is correct
14 Correct 5 ms 4224 KB Output is correct
15 Correct 6 ms 4352 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB Output is correct
2 Correct 4 ms 4224 KB Output is correct
3 Correct 6 ms 4224 KB Output is correct
4 Correct 6 ms 4352 KB Output is correct
5 Correct 6 ms 4352 KB Output is correct
6 Correct 6 ms 4288 KB Output is correct
7 Correct 6 ms 4352 KB Output is correct
8 Correct 6 ms 4272 KB Output is correct
9 Correct 8 ms 4608 KB Output is correct
10 Correct 5 ms 4224 KB Output is correct
11 Correct 6 ms 4352 KB Output is correct
12 Correct 10 ms 4780 KB Output is correct
13 Correct 10 ms 4860 KB Output is correct
14 Correct 5 ms 4224 KB Output is correct
15 Correct 6 ms 4352 KB Output is correct
16 Correct 755 ms 65812 KB Output is correct
17 Correct 101 ms 15736 KB Output is correct
18 Correct 134 ms 17368 KB Output is correct
19 Correct 898 ms 68348 KB Output is correct
20 Correct 505 ms 55400 KB Output is correct
21 Correct 51 ms 9464 KB Output is correct
22 Correct 433 ms 48068 KB Output is correct