oj.uz

Submission #118858

# Submission time Handle Problem Language Result Execution time Memory
118858 2019-06-19T23:59:32 Z CaroLinda Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 886 ms 262144 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(v[t.ss].secondBest.ff == -t.ff)
			{
				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 6 ms 4224 KB Output is correct
2 Correct 5 ms 4224 KB Output is correct
3 Correct 6 ms 4352 KB Output is correct
4 Correct 6 ms 4352 KB Output is correct
5 Correct 6 ms 4480 KB Output is correct
6 Correct 6 ms 4352 KB Output is correct
7 Correct 6 ms 4352 KB Output is correct
8 Correct 6 ms 4352 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4224 KB Output is correct
2 Correct 5 ms 4224 KB Output is correct
3 Correct 6 ms 4352 KB Output is correct
4 Correct 6 ms 4352 KB Output is correct
5 Correct 6 ms 4480 KB Output is correct
6 Correct 6 ms 4352 KB Output is correct
7 Correct 6 ms 4352 KB Output is correct
8 Correct 6 ms 4352 KB Output is correct
9 Runtime error 886 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4224 KB Output is correct
2 Correct 5 ms 4224 KB Output is correct
3 Correct 6 ms 4352 KB Output is correct
4 Correct 6 ms 4352 KB Output is correct
5 Correct 6 ms 4480 KB Output is correct
6 Correct 6 ms 4352 KB Output is correct
7 Correct 6 ms 4352 KB Output is correct
8 Correct 6 ms 4352 KB Output is correct
9 Runtime error 886 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -