# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
65177 | kingpig9 | Evacuation plan (IZhO18_plan) | C++11 | 1483 ms | 20992 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 10, INF = 1e8;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N, M;
vector<pii> adj[MAXN];
struct union_find {
int par[MAXN];
void reset() {
for (int i = 0; i < N; i++) {
par[i] = i;
}
}
int find (int x) {
return x == par[x] ? x : par[x] = find(par[x]);
}
void merge (int x, int y) {
par[find(x)] = find(y);
}
} uf;
int K, G[MAXN];
int dist[MAXN];
bool vis[MAXN];
int dord[MAXN]; //order of dist
int Q;
int S[MAXN], T[MAXN];
int ind[MAXN], lo[MAXN], hi[MAXN], mid[MAXN];
//code for dijkstra
void dijkstra() {
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 0; i < N; i++) {
dist[i] = INF;
}
for (int i = 0; i < K; i++) {
int x = G[i];
dist[x] = 0;
pq.push({0, x});
}
while (!pq.empty()) {
int u = pq.top().se, w = pq.top().fi;
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
for (pii e : adj[u]) {
int v = e.se;
int nw = e.fi + w;
if (dist[v] > nw) {
dist[v] = nw;
pq.push({nw, v});
}
}
}
/*
for (int i = 0; i < N; i++) {
debug("dist[%d] = %d\n", i, dist[i]);
}
*/
}
bool cmpd (int x, int y) {
return dist[x] > dist[y];
}
bool cmp (int x, int y) {
return mid[x] > mid[y];
}
int main() {
scanf("%d %d", &N, &M);
for (int i = 0; i < M; i++) {
int a, b, w;
scanf("%d %d %d", &a, &b, &w);
a--;
b--;
adj[a].push_back({w, b});
adj[b].push_back({w, a});
}
scanf("%d", &K);
for (int i = 0; i < K; i++) {
scanf("%d", &G[i]);
G[i]--;
}
dijkstra();
scanf("%d", &Q);
for (int i = 0; i < Q; i++) {
scanf("%d %d", &S[i], &T[i]);
S[i]--;
T[i]--;
lo[i] = 0; //ans always >= lo[i], always < hi[i]
hi[i] = INF;
}
iota(dord, dord + N, 0);
sort(dord, dord + N, cmpd);
//code for parallel bsearch
for (int iter = 0; iter < 28; iter++) {
for (int i = 0; i < Q; i++) {
mid[i] = (lo[i] + hi[i]) / 2;
ind[i] = i;
}
sort(ind, ind + Q, cmp);
uf.reset();
int dptr = 0;
for (int ii = 0; ii < Q; ii++) {
int i = ind[ii];
for (; dptr < N && dist[dord[dptr]] >= mid[i]; dptr++) {
//try to merge if you can
int x = dord[dptr];
for (pii e : adj[x]) {
int y = e.se;
if (dist[y] >= mid[i]) {
uf.merge(x, y);
}
}
}
if (uf.find(S[i]) == uf.find(T[i])) {
lo[i] = mid[i];
} else {
hi[i] = mid[i];
}
}
}
//code for final output
for (int i = 0; i < Q; i++) {
printf("%d\n", lo[i]);
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |