oj.uz

Submission #338787

# Submission time Handle Problem Language Result Execution time Memory
338787 2020-12-23T22:29:56 Z CSQ31 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 657 ms 90084 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (int)(a.size())
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll A,ll B) {if(!B)return A;return gcd(B,A%B);}
vector<vector<PII>> adj(100010);
vector<ll>dist(100010,INF);
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for(int i=0;i<M;i++){
		adj[R[i][1]].pb({R[i][0],L[i]});
		adj[R[i][0]].pb({R[i][1],L[i]});
	}
	priority_queue<PII,vector<PII>,greater<PII>>pq;
	for(int i=0;i<K;i++){
		pq.push({0,P[i]});
		dist[P[i]] = 0;
	}
	vector<PII>mn(N,{INF,INF});
	while(!pq.empty()){
		int v = pq.top().se;
		ll d = pq.top().fi;
		pq.pop();
		if(d != dist[v])continue;
		//cout<<d<<" "<<v<<'\n';
		for(auto x:adj[v]){
			int to = x.fi;
			ll w = x.se;
			if(mn[to].fi == INF)mn[to].fi = w+d;
			else{
				if(mn[to].se == INF){mn[to].se = w+d;if(mn[to].fi > mn[to].se)swap(mn[to].fi,mn[to].se);}
				else if(mn[to].se > w+d){
					if(mn[to].fi >= w+d){
						mn[to].se = mn[to].fi;
						mn[to].fi = w+d;
					}else{
						mn[to].se = w+d;
					}
				}
			}
			//cout<<to<<" "<<mn[to].fi<<" "<<mn[to].se<<'\n';
			if(mn[to].se != INF && mn[to].se < dist[to]){
				dist[to] = mn[to].se;
				pq.push({dist[to],to});
			}
		}
		
	}
	return dist[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3436 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 3 ms 3436 KB Output is correct
4 Correct 3 ms 3564 KB Output is correct
5 Correct 3 ms 3564 KB Output is correct
6 Correct 3 ms 3564 KB Output is correct
7 Correct 3 ms 3564 KB Output is correct
8 Correct 3 ms 3564 KB Output is correct
9 Correct 4 ms 3948 KB Output is correct
10 Correct 2 ms 3436 KB Output is correct
11 Correct 3 ms 3692 KB Output is correct
12 Correct 7 ms 4332 KB Output is correct
13 Correct 8 ms 4332 KB Output is correct
14 Correct 3 ms 3564 KB Output is correct
15 Correct 4 ms 3564 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3436 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 3 ms 3436 KB Output is correct
4 Correct 3 ms 3564 KB Output is correct
5 Correct 3 ms 3564 KB Output is correct
6 Correct 3 ms 3564 KB Output is correct
7 Correct 3 ms 3564 KB Output is correct
8 Correct 3 ms 3564 KB Output is correct
9 Correct 4 ms 3948 KB Output is correct
10 Correct 2 ms 3436 KB Output is correct
11 Correct 3 ms 3692 KB Output is correct
12 Correct 7 ms 4332 KB Output is correct
13 Correct 8 ms 4332 KB Output is correct
14 Correct 3 ms 3564 KB Output is correct
15 Correct 4 ms 3564 KB Output is correct
16 Correct 532 ms 83812 KB Output is correct
17 Correct 85 ms 18764 KB Output is correct
18 Correct 106 ms 20908 KB Output is correct
19 Correct 657 ms 90084 KB Output is correct
20 Correct 311 ms 68460 KB Output is correct
21 Correct 40 ms 10604 KB Output is correct
22 Correct 330 ms 65004 KB Output is correct