Submission #909875

#	Time	Username	Problem	Language	Result	Execution time	Memory
909875		ByeWorld	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	444 ms	95176 KiB

crocodile

#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 (stderr)

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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11