oj.uz

Submission #229393

# Submission time Handle Problem Language Result Execution time Memory
229393 2020-05-04T11:46:42 Z kshitij_sodani Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 908 ms 90476 KB 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
#include <crocodile.h>
llo ma=1000000001;
int travel_plan(int n,int m,int r[][2],int l[],int k,int p[]){
	llo vis[n];
	for(llo i=0;i<n;i++){
		vis[i]=0;
	}
	for(llo i=0;i<k;i++){
		vis[p[i]]=1;
	}
	vector<pair<llo,llo>> adj[n];
	for(llo i=0;i<m;i++){
		adj[r[i][0]].pb({r[i][1],(llo)l[i]});
		adj[r[i][1]].pb({r[i][0],(llo)l[i]});
	}
	llo dist[n];
	llo dist2[n];
	for(llo i=0;i<n;i++){
		dist[i]=ma;
		dist2[i]=ma;
	}
	priority_queue<pair<llo,llo>> ac;
	for(llo i=0;i<n;i++){
		if(vis[i]==1){
			dist[i]=0;
			dist2[i]=0;
			ac.push({0,i});
		}	
	}
	int vis2[n];
	for(int i=0;i<n;i++){
		vis2[i]=0;
	}
	while(ac.size()){
		pair<llo,llo> no=ac.top();
		ac.pop();
		no.a=-no.a;
		if(vis2[no.b]==1){
			continue;
		}
		vis2[no.b]=1;
		for(auto j:adj[no.b]){
			llo co=dist2[no.b]+j.b;
			if(dist[j.a]>=co){
				llo acc=dist2[j.a];
				dist2[j.a]=dist[j.a];
				dist[j.a]=co;
				if(dist2[j.a]!=acc){
					ac.push({-dist2[j.a],j.a});
				}
			}
			else if(dist2[j.a]>co){
				dist2[j.a]=co;
				ac.push({-dist2[j.a],j.a});
			}
		}
	}
	return dist2[0];
}
/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,m,k;
	cin>>n>>m>>k;
	llo rr[m][2];
	llo l[m];
	llo pp[k];
	for(llo i=0;i<m;i++){
		cin>>rr[i][0]>>rr[i][1]>>l[i];
	}
	for(llo i=0;i<k;i++){
		cin>>pp[i];
	}
	cout<<travel_plan(n,m,rr,l,k,pp)<<endl;
	llo aa[7][2];
	llo bb[7];
	llo cc[2];
	cc[0]=1;cc[1]=3;
	bb[0]=4;bb[1]=3;bb[2]=2;bb[3]=10;bb[4]=100;
	bb[5]=7;bb[6]=9;
	aa[0][0]=0;aa[0][1]=2;
	aa[1][0]=0;aa[1][1]=3;
	aa[2][0]=3;aa[2][1]=2;
	aa[3][0]=2;aa[3][1]=1;
	aa[4][0]=0;aa[4][1]=1;
	aa[5][0]=0;aa[5][1]=4;
	aa[6][0]=3;aa[6][1]=4;
 
	llo aa[4][2];
	llo bb[4];
	llo cc[3];
	cc[0]=1;cc[1]=3;cc[2]=4;
	bb[0]=2;bb[1]=3;bb[2]=1;bb[3]=4;
	aa[0][0]=0;aa[0][1]=1;
	aa[1][0]=0;aa[1][1]=2;
	aa[2][0]=3;aa[2][1]=2;
	aa[3][0]=2;aa[3][1]=4;
	cout<<travel_plan(5,4,aa,bb,3,cc)<<endl;
 
	return 0;
}*/

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 768 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 10 ms 1024 KB Output is correct
13 Correct 10 ms 1152 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 512 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 768 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 10 ms 1024 KB Output is correct
13 Correct 10 ms 1152 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 747 ms 81588 KB Output is correct
17 Correct 133 ms 18808 KB Output is correct
18 Correct 151 ms 21344 KB Output is correct
19 Correct 908 ms 90476 KB Output is correct
20 Correct 479 ms 65144 KB Output is correct
21 Correct 64 ms 8568 KB Output is correct
22 Correct 521 ms 62840 KB Output is correct