oj.uz

Submission #909877

# Submission time Handle Problem Language Result Execution time Memory
909877 2024-01-17T14:07:07 Z ByeWorld Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 454 ms 80836 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define bupol __builtin_popcount
//#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 1e5+5;
const int MAXK = 205;
const int LOG = 20;
const int MOD = 1e9+7;
const int SQRT = 520;
const ll INF = 1e18;
const ll INF2 = 1e9;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
 
int n, m, k;
int ty[MAXN], vis[MAXN];
vector <pii> adj[MAXN];
priority_queue <ipii, vector<ipii>, greater<ipii>> pq;
ll dis[MAXN], dis2[MAXN]; // dis kalo udh termasuk milih kedua
 
int cnt = 0;
void dji(){
	for(int i=0; i<n; i++){
		dis[i] = INF; dis2[i] = INF;
		if(ty[i]){
			dis[i] = 0; pq.push({{0, 0}, i});
			dis2[i] = 0;
		}
	}
 
	while(!pq.empty()){ //isinya dis2, nw
		ll D1 = pq.top().fi.fi, D2 = pq.top().fi.se, nw = pq.top().se;
		pq.pop();
		if(vis[nw]) continue; //dis1 <= dis2
		vis[nw] = 1;
		//cout << D1 << ' ' << D2 << ' ' << nw << " nw\n";
 
		for(auto ed : adj[nw]){
			ll nx = ed.fi, wei = ed.se;
			if(dis[nx] >= dis2[nw] + wei ){
				dis2[nx] = dis[nx]; //swap
				dis[nx] = dis2[nw] + wei;
 
				if(max(dis[nx], dis2[nx]) < INF2)
					pq.push(ipii( pii(dis2[nx], dis[nx]), nx) );
 
			} else if(dis2[nx] >= dis2[nw] + wei ){
				dis2[nx] = dis2[nw] + wei ;
 
				if(max(dis[nx], dis2[nx]) < INF2)
					pq.push(ipii( pii(dis2[nx], dis[nx]), nx) );
			}
		}
	}
}
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	n = N; m = M; k = K;
	for(int i=0; i<k; i++){
		ty[P[i]] = 1;
	}
	for(int i=0; i<m; i++){
		int x = R[i][0], y = R[i][1], w = L[i];
		adj[x].pb({y, w}); adj[y].pb({x, w});
	}
 
	dji();
	return (int)(max(dis[0], dis2[0]));
}

Compilation message

crocodile.cpp: In function 'void dji()':
crocodile.cpp:41:6: warning: unused variable 'D1' [-Wunused-variable]
   41 |   ll D1 = pq.top().fi.fi, D2 = pq.top().fi.se, nw = pq.top().se;
      |      ^~
crocodile.cpp:41:27: warning: unused variable 'D2' [-Wunused-variable]
   41 |   ll D1 = pq.top().fi.fi, D2 = pq.top().fi.se, nw = pq.top().se;
      |                           ^~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8756 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 4 ms 8792 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 4 ms 9048 KB Output is correct
13 Correct 5 ms 9048 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8792 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8756 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 4 ms 8792 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 4 ms 9048 KB Output is correct
13 Correct 5 ms 9048 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8792 KB Output is correct
16 Correct 338 ms 73776 KB Output is correct
17 Correct 58 ms 18512 KB Output is correct
18 Correct 87 ms 21332 KB Output is correct
19 Correct 454 ms 80836 KB Output is correct
20 Correct 233 ms 61776 KB Output is correct
21 Correct 28 ms 12880 KB Output is correct
22 Correct 248 ms 55376 KB Output is correct