oj.uz

Submission #29259

# Submission time Handle Problem Language Result Execution time Memory
29259 2017-07-18T20:28:45 Z dereotu Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1409 ms 174968 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define forr(i,A,B) for(int i=A;i<B;++i)
#define space ' '
#define endl '\n'
#define LL long long
#define exit adsjdsa
using namespace std;
int exit[100005];
vector <pair<int,int> > adj[100005];
int weight[100005];
int vis[100005];
int ans,n;

void dijkstra(){
	priority_queue <pair<int,int> > pq;
	forr(i,0,n){
		if(exit[i]){
			pq.push(mp(0,i));
			vis[i]=1;
		}
	}
	while(!pq.empty()){
		int v=pq.top().nd;
		int w=-pq.top().st;
		pq.pop();
		if(vis[v]==1){
			weight[v]=-w;
			forr(i,0,adj[v].size()){
				pq.push(mp(-w-adj[v][i].st,adj[v][i].nd));
			}
		}
		vis[v]++;
	}
	ans=-weight[0];
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	forr(i,0,M){
		adj[R[i][0]].pb(mp(L[i],R[i][1]));
		adj[R[i][1]].pb(mp(L[i],R[i][0]));
	}
	forr(i,0,K){
		exit[P[i]]=1;
	}
	n=N;
	dijkstra();
	return ans;
}

Compilation message

crocodile.cpp: In function 'void dijkstra()':
crocodile.cpp:8:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,A,B) for(int i=A;i<B;++i)
                                  ^
crocodile.cpp:34:4: note: in expansion of macro 'forr'
    forr(i,0,adj[v].size()){
    ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122916 KB Output is correct
2 Correct 0 ms 122916 KB Output is correct
3 Correct 0 ms 122916 KB Output is correct
4 Correct 3 ms 123048 KB Output is correct
5 Correct 3 ms 123052 KB Output is correct
6 Correct 0 ms 122916 KB Output is correct
7 Correct 0 ms 123048 KB Output is correct
8 Correct 0 ms 122916 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 123324 KB Output is correct
2 Correct 0 ms 122916 KB Output is correct
3 Correct 3 ms 123048 KB Output is correct
4 Correct 6 ms 123604 KB Output is correct
5 Correct 0 ms 123684 KB Output is correct
6 Correct 0 ms 122916 KB Output is correct
7 Correct 0 ms 123048 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1279 ms 172608 KB Output is correct
2 Correct 103 ms 127668 KB Output is correct
3 Correct 149 ms 128856 KB Output is correct
4 Correct 1409 ms 174968 KB Output is correct
5 Correct 806 ms 170468 KB Output is correct
6 Correct 56 ms 125292 KB Output is correct
7 Correct 689 ms 142052 KB Output is correct