oj.uz

Submission #72843

# Submission time Handle Problem Language Result Execution time Memory
72843 2018-08-27T05:16:55 Z TuGSGeReL Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 932 ms 45180 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back
#define ss second
#define ff first
#define ext exit(0)
using namespace std;
int i,mn1[100001],mn2[100001];
vector<pair<int,int> >v[100001];
priority_queue<pair<int,int> >q;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for(i=0;i<M;i++){
		v[R[i][0]].pub(mp(R[i][1],L[i]));
		v[R[i][1]].pub(mp(R[i][0],L[i]));
	}
	memset(mn2,63,sizeof mn2);
	memset(mn1,63,sizeof mn1);
	for(i=0;i<K;i++){
		q.push(mp(0,P[i]));
		mn1[P[i]]=0;
		mn2[P[i]]=0;
	}
	while(!q.empty()){
		int idx=q.top().ss,cs=-q.top().ff;
		q.pop();
		if(cs>mn2[idx]) continue;
		for(i=0;i<v[idx].size();i++){
			int idx1=v[idx][i].ff,cst1=v[idx][i].ss;
			int cstdt=mn2[idx1];
			mn2[idx1]=min(mn2[idx1],cs+cst1);
			if(mn2[idx1]<mn1[idx1])swap(mn2[idx1],mn1[idx1]);
			if(mn2[idx1]!=cstdt) q.push(mp(-mn2[idx1],idx1));
		}
	}
	return mn2[0];
}

Compilation message

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

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 6 ms 3592 KB Output is correct
4 Correct 6 ms 3668 KB Output is correct
5 Correct 7 ms 3748 KB Output is correct
6 Correct 6 ms 3748 KB Output is correct
7 Correct 7 ms 3748 KB Output is correct
8 Correct 5 ms 3748 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 6 ms 3592 KB Output is correct
4 Correct 6 ms 3668 KB Output is correct
5 Correct 7 ms 3748 KB Output is correct
6 Correct 6 ms 3748 KB Output is correct
7 Correct 7 ms 3748 KB Output is correct
8 Correct 5 ms 3748 KB Output is correct
9 Correct 7 ms 3872 KB Output is correct
10 Correct 5 ms 3872 KB Output is correct
11 Correct 5 ms 3872 KB Output is correct
12 Correct 8 ms 4000 KB Output is correct
13 Correct 9 ms 4128 KB Output is correct
14 Correct 6 ms 4128 KB Output is correct
15 Correct 7 ms 4128 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 6 ms 3592 KB Output is correct
4 Correct 6 ms 3668 KB Output is correct
5 Correct 7 ms 3748 KB Output is correct
6 Correct 6 ms 3748 KB Output is correct
7 Correct 7 ms 3748 KB Output is correct
8 Correct 5 ms 3748 KB Output is correct
9 Correct 7 ms 3872 KB Output is correct
10 Correct 5 ms 3872 KB Output is correct
11 Correct 5 ms 3872 KB Output is correct
12 Correct 8 ms 4000 KB Output is correct
13 Correct 9 ms 4128 KB Output is correct
14 Correct 6 ms 4128 KB Output is correct
15 Correct 7 ms 4128 KB Output is correct
16 Correct 759 ms 41724 KB Output is correct
17 Correct 108 ms 41724 KB Output is correct
18 Correct 154 ms 41724 KB Output is correct
19 Correct 932 ms 45180 KB Output is correct
20 Correct 472 ms 45180 KB Output is correct
21 Correct 53 ms 45180 KB Output is correct
22 Correct 461 ms 45180 KB Output is correct