oj.uz

답안 #909852

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
909852 2024-01-17T13:37:58 Z ByeWorld 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 3 ms 8540 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]) continue; //dis1 <= dis2
		if(D2 > dis2[nw]) continue;
		cnt++;
		// if(cnt < 10)
		// 	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();
	return dis2[0];
}

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -