제출 #66134

#제출 시각아이디문제언어결과실행 시간메모리
66134kingpig9Evacuation plan (IZhO18_plan)C++11
100 / 100
786 ms43912 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MAXN = 1e5 + 10; const int MAXLG = 17; const int 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]); } bool merge (int x, int y) { x = find(x); y = find(y); if (x == y) { return false; } par[x] = y; return true; } } uf; int K, G[MAXN]; int dist[MAXN]; bool vis[MAXN]; int Q; //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]); } */ } vector<pii> tree[MAXN]; int par[MAXN][MAXLG]; int mnw[MAXN][MAXLG]; int depth[MAXN]; void dfs (int x) { for (pii e : tree[x]) { int w = e.fi; int y = e.se; for (auto it = tree[y].begin(); ; it++) { if (it->se == x) { tree[y].erase(it); break; } } depth[y] = depth[x] + 1; par[y][0] = x; mnw[y][0] = w; for (int i = 1; i < MAXLG; i++) { int pp = par[par[y][i - 1]][i - 1]; if (pp == -1) { break; } par[y][i] = pp; mnw[y][i] = min(mnw[y][i - 1], mnw[par[y][i - 1]][i - 1]); } dfs(y); } } int getpar (int x, int d) { for (int i = 0; d; i++, d >>= 1) { if (d & 1) { x = par[x][i]; } } return x; } int lca (int x, int y) { if (depth[x] < depth[y]) { swap(x, y); } x = getpar(x, depth[x] - depth[y]); if (x == y) { return x; } for (int i = MAXLG - 1; i >= 0; i--) { if (par[x][i] != par[y][i]) { x = par[x][i]; y = par[y][i]; } } return par[x][0]; } int minjump (int x, int d) { if (d == 0) { return INT_MAX; } int res = INT_MAX; for (int i = 0; d; i++, d >>= 1) { if (d & 1) { res = min(res, mnw[x][i]); x = par[x][i]; } } return res; } int getmin (int x, int y) { int c = lca(x, y); return min(minjump(x, depth[x] - depth[c]), minjump(y, depth[y] - depth[c])); } 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(); vector<array<int, 3>> edges; for (int i = 0; i < N; i++) { for (pii e : adj[i]) { int j = e.se; //min bottleneck path if (i < j) { edges.push_back({min(dist[i], dist[j]), i, j}); } } } sort(edges.rbegin(), edges.rend()); uf.reset(); for (auto e : edges) { if (uf.merge(e[1], e[2])) { //debug("TREE EDGE %d %d %d\n", e[1], e[2], e[0]); tree[e[1]].push_back({e[0], e[2]}); tree[e[2]].push_back({e[0], e[1]}); } } fillchar(par, -1); dfs(0); scanf("%d", &Q); for (int i = 0; i < Q; i++) { int s, t; scanf("%d %d", &s, &t); printf("%d\n", getmin(s - 1, t - 1)); } }

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'int main()':
plan.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:171:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &K);
  ~~~~~^~~~~~~~~~
plan.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &G[i]);
   ~~~~~^~~~~~~~~~~~~
plan.cpp:209:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
plan.cpp:212:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &s, &t);
   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...