oj.uz

Submission #909875

# Submission time Handle Problem Language Result Execution time Memory
909875 2024-01-17T14:05:55 Z ByeWorld Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 444 ms 95176 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 <pii, vector<pii>, greater<pii>> 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, i});
			dis2[i] = 0;
		}
	}

	while(!pq.empty()){ //isinya dis2, nw
		ll D1 = pq.top().fi, nw = pq.top().se;
		pq.pop();
		if(vis[nw]) continue; //dis1 <= dis2
		vis[nw] = 1;
		//cout << D1  << ' ' << 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(pii(dis2[nx], nx) );

			} else if(dis2[nx] >= dis2[nw] + wei ){
				dis2[nx] = dis2[nw] + wei ;

				if(max(dis[nx], dis2[nx]) < INF2)
					pq.push(pii(dis2[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, nw = pq.top().se;
      |      ^~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8692 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8652 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8536 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 5 ms 8792 KB Output is correct
10 Correct 2 ms 8536 KB Output is correct
11 Correct 4 ms 8796 KB Output is correct
12 Correct 5 ms 9052 KB Output is correct
13 Correct 5 ms 9304 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 3 ms 8540 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8692 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8652 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8536 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 5 ms 8792 KB Output is correct
10 Correct 2 ms 8536 KB Output is correct
11 Correct 4 ms 8796 KB Output is correct
12 Correct 5 ms 9052 KB Output is correct
13 Correct 5 ms 9304 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 3 ms 8540 KB Output is correct
16 Correct 350 ms 88808 KB Output is correct
17 Correct 72 ms 21836 KB Output is correct
18 Correct 84 ms 24112 KB Output is correct
19 Correct 444 ms 95176 KB Output is correct
20 Correct 234 ms 74580 KB Output is correct
21 Correct 28 ms 14172 KB Output is correct
22 Correct 246 ms 69324 KB Output is correct