oj.uz

Submission #197831

# Submission time Handle Problem Language Result Execution time Memory
197831 2020-01-23T15:03:14 Z Sakamotoo Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 2 ms 376 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;

#define mp make_pair
#define fi first
#define se second

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
	vector<pair<int,int> > adj[n];
	long long a[n],b[n];
	for(int i=0; i<n; i++){
		a[i]=1e18;
		b[i]=1e18;
	}
	int s[n];
	memset(s,0,sizeof s);
	for(int i=0; i<k; i++){
		s[p[i]]=1;
	}
	for(int i=0; i<m; i++){
		int x=r[i][0],y=r[i][1];
		if(s[y]==1) swap(x,y);
		long long sim=l[i];
		if(s[x]==1){
			if(a[y]>sim){
				swap(a[y],sim);
			}
			if(b[y]>sim){
				swap(b[y],sim);
			}
		}else {
			adj[x].push_back(mp(y,sim));
			adj[y].push_back(mp(x,sim));
		}
	}
	priority_queue<pair<long long, long long> > pq;
	for(int i=0; i<n; i++){
		if(b[i]<1e18&&s[i]==0){
			pq.push(mp(b[i],i));
		}
	}
	while(!pq.empty()){
		long long x=pq.top().fi,y=pq.top().se;
		pq.pop();
		if(x>b[y]) continue;
		for(int i=0; i<adj[y].size(); i++){
			long long z=adj[y][i].fi;
			long long c=adj[y][i].se+x;
			bool ada=0;
			if(c<a[z]){
				ada=1;
				swap(c,a[z]);
			}
			if(c<b[z]){
				ada=1;
				swap(c,b[z]);
			}
			if(ada)pq.push(mp(b[z],z));
		}
	}
	return b[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<adj[y].size(); i++){
                ~^~~~~~~~~~~~~~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -