oj.uz

Submission #909863

# Submission time Handle Problem Language Result Execution time Memory
909863 2024-01-17T13:54:39 Z ByeWorld Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 2 ms 8536 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;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;

int n, m, k;
int ty[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(D1 > dis[nw] ||  D2 > dis2[nw]) continue; //dis1 <= dis2
		cnt++;
		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;

				pq.push(ipii( pii(dis[nx], dis2[nx]), nx) );

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

				pq.push(ipii( pii(dis[nx], 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();
	if(dis2[0] > 1000000000){
		return -1;
		assert(false);
	}
	return dis2[0];
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -