oj.uz

Submission #43876

# Submission time Handle Problem Language Result Execution time Memory
43876 2018-03-26T15:38:29 Z faustaadp Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1431 ms 132084 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll d[2][101010],i;
vector<ll> v[101010],w[101010];
priority_queue<pair<ll,ll> > pq;
pair<ll,ll> u;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	memset(d,-1,sizeof(d));
	for(i=0;i<M;i++)
	{
		v[R[i][0]].pb(R[i][1]);
		w[R[i][0]].pb(L[i]);
		v[R[i][1]].pb(R[i][0]);
		w[R[i][1]].pb(L[i]);
	}
	for(i=0;i<K;i++)
	{
		d[0][P[i]]=0;
		pq.push(mp(0,P[i]));
	}
	while(!pq.empty())
	{
		u=pq.top();
		pq.pop();
		if(d[0][u.se]==-1)
			d[0][u.se]=-u.fi;
		else
		if(d[1][u.se]==-1)
		{
			d[1][u.se]=-u.fi;
			for(i=0;i<v[u.se].size();i++)
				if(d[0][v[u.se][i]]==-1||d[1][v[u.se][i]]==-1)	
					pq.push(mp(u.fi-w[u.se][i],v[u.se][i]));
		}
	}
  	return d[1][0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:38:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v[u.se].size();i++)
            ~^~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6648 KB Output is correct
2 Correct 7 ms 6768 KB Output is correct
3 Correct 6 ms 6880 KB Output is correct
4 Correct 7 ms 7064 KB Output is correct
5 Correct 7 ms 7192 KB Output is correct
6 Correct 8 ms 7192 KB Output is correct
7 Correct 7 ms 7192 KB Output is correct
8 Correct 7 ms 7200 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7856 KB Output is correct
2 Correct 6 ms 7856 KB Output is correct
3 Correct 7 ms 7856 KB Output is correct
4 Correct 12 ms 8356 KB Output is correct
5 Correct 12 ms 8600 KB Output is correct
6 Correct 7 ms 8600 KB Output is correct
7 Correct 7 ms 8600 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1210 ms 100556 KB Output is correct
2 Correct 131 ms 100556 KB Output is correct
3 Correct 180 ms 100556 KB Output is correct
4 Correct 1431 ms 128288 KB Output is correct
5 Correct 602 ms 132084 KB Output is correct
6 Correct 65 ms 132084 KB Output is correct
7 Correct 577 ms 132084 KB Output is correct