oj.uz

Submission #522344

# Submission time Handle Problem Language Result Execution time Memory
522344 2022-02-04T16:07:33 Z new_acc Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1555 ms 129248 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (int)(b); a++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
vector<pair<int,ll> > graf[N];
int vis[N];
ll travel_plan(int n,int m,int r[][2],int l[],int k,int p[]){
	rep(i,m) graf[r[i][0]].push_back({r[i][1],l[i]}),graf[r[i][1]].push_back({r[i][0],l[i]});
	multiset<pair<ll,int> >s;
	rep(i,k) s.insert({0,p[i]}),vis[p[i]]=1;
	while(!s.empty()){
		auto it=s.begin();
		s.erase(it);
		int v=(*it).se;
		ll c=(*it).fi;
		if(vis[v]==0){vis[v]=1;continue;}
		if(vis[v]>1) continue;
		vis[v]++;
		if(v==0) return c;
		for(auto u:graf[v]){
			ll c2=c+u.se;
			if(vis[u.fi]<2) s.insert({c2,u.fi});
		}
	}
	return 0;
}
/*int main(){
	int n,m,k;
	cin>>n>>m>>k;
	int r[m][2],l[m],p[k];
	rep(i,m) cin>>r[i][0]>>r[i][1]>>l[i];

	rep(i,k) cin>>p[i];
	cout<<travel_plan(n,m,r,l,k,p)<<"\n";
}*/

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 2 ms 2664 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 4 ms 3148 KB Output is correct
10 Correct 2 ms 2664 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 7 ms 3820 KB Output is correct
13 Correct 5 ms 3444 KB Output is correct
14 Correct 2 ms 2660 KB Output is correct
15 Correct 2 ms 2788 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 2 ms 2664 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 4 ms 3148 KB Output is correct
10 Correct 2 ms 2664 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 7 ms 3820 KB Output is correct
13 Correct 5 ms 3444 KB Output is correct
14 Correct 2 ms 2660 KB Output is correct
15 Correct 2 ms 2788 KB Output is correct
16 Correct 1555 ms 129248 KB Output is correct
17 Correct 79 ms 16484 KB Output is correct
18 Correct 115 ms 18812 KB Output is correct
19 Correct 1194 ms 114796 KB Output is correct
20 Correct 281 ms 67948 KB Output is correct
21 Correct 45 ms 9284 KB Output is correct
22 Correct 522 ms 65168 KB Output is correct