oj.uz

Submission #462381

# Submission time Handle Problem Language Result Execution time Memory
462381 2021-08-10T12:47:29 Z Khizri Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 540 ms 90092 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=1e5+5;
ll isexit[mxn],color[mxn],n,m,arr[mxn],dis[mxn][2];
vector<pll>vt[mxn];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	n=N,m=M;
	for(int i=0;i<m;i++){
		vt[R[i][0]].pb({R[i][1],L[i]});
		vt[R[i][1]].pb({R[i][0],L[i]});
	}
	priority_queue<pll,vector<pll>,greater<pll>>q;
	for(int i=0;i<n;i++){
		dis[i][0]=dis[i][1]=INF;
	}
	for(int i=0;i<K;i++){
		q.push({0,P[i]});
		dis[P[i]][0]=dis[P[i]][1]=0;
	}
	while(q.size()){
		pll p=q.top();
		q.pop();
		ll u=p.S,sum=p.F;
		if(u==0){
			return sum;
		}
		if(color[u]){
			continue;
		}
		color[u]=1;
		for(pll xx:vt[u]){
			int v=xx.F,x=xx.S;
			if(dis[v][0]>dis[u][1]+x){
				dis[v][1]=dis[v][0];
				dis[v][0]=dis[u][1]+x;
				if(dis[v][1]!=INF){
					q.push({dis[v][1],v});
				}
			}
			else if(dis[v][1]>dis[u][1]+x){
				dis[v][1]=dis[u][1]+x;
				q.push({dis[v][1],v});
			}
		}
	}
	return 0;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 4 ms 3020 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 6 ms 3400 KB Output is correct
13 Correct 5 ms 3432 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 4 ms 3020 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 6 ms 3400 KB Output is correct
13 Correct 5 ms 3432 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct
16 Correct 469 ms 83260 KB Output is correct
17 Correct 85 ms 18372 KB Output is correct
18 Correct 98 ms 20804 KB Output is correct
19 Correct 540 ms 90092 KB Output is correct
20 Correct 315 ms 68036 KB Output is correct
21 Correct 41 ms 9924 KB Output is correct
22 Correct 342 ms 64308 KB Output is correct