제출 #971997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971997		Sunbae	Evacuation plan (IZhO18_plan)	C++17	19 / 100	371 ms	71852 KiB

plan

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using pli = pair<ll,int>;
const int N = 1e5 + 5, M = 5e5 + 5;
const ll inf = 1e18; // beaware maybe not enough
vector<pli> adj[N];
ll D[N], mn[N][20];
bool vis[N];
tuple<int,int,int> E[M];
tuple<ll,int,int> edges[M];
int p[N], up[N][20], dep[N], LOG, sz[N];
int fp(int x){if(x == p[x]) return x; return p[x] = fp(p[x]);}
void dfs(int u, int p, ll wp){
	up[u][0] = p; mn[u][0] = min(mn[u][0], wp);
	if(u != p) dep[u] = dep[p] + 1;
	for(int j = 1; j<LOG; ++j){
		up[u][j] = up[up[u][j-1]][j-1];
		mn[u][j] = min(mn[u][j-1], mn[up[u][j-1]][j-1]);
	}
	for(pli it: adj[u]){
		ll w = it.first; int v = it.second;
		if(v != p) dfs(v, u, w);
	}
}
pair<ll,int> get_lca(int u, int v){
	ll w = inf;
	if(u == v) return make_pair(w, u);
	if(dep[u] < dep[v]) swap(u, v);
	for(int j = LOG-1; j>=0; --j) if((dep[u]-dep[v])>>j&1) w = min(w, mn[u][j]), u = up[u][j];
	if(u == v) return make_pair(w, u);
	for(int j = LOG-1; j>=0; --j) if(up[u][j] != up[v][j]){w = min({w, mn[u][j], mn[v][j]}); u = up[u][j]; v = up[v][j];}
	return make_pair(min(w, mn[u][0]), up[u][0]);
}
signed main(){
	int n, m; scanf("%d %d", &n, &m); LOG = 32 - __builtin_clz(n);
	for(int i = 0, u, v, w; i<m; ++i){
		scanf("%d %d %d", &u, &v, &w); --u; --v;
		E[i] = make_tuple(u, v, w);
		adj[u].emplace_back(w, v); adj[v].emplace_back(w, u);
	}
	priority_queue<pli, vector<pli>, greater<pli>> pq;
	fill(D, D+n, inf); fill(vis, vis+n, false);
	int k; scanf("%d", &k);
	for(int i = 0, u; i<k; ++i) scanf("%d", &u), pq.emplace(D[u-1] = 0, u-1);
	while(!pq.empty()){
		int u = pq.top().second; pq.pop();
		if(vis[u]) continue; vis[u] = true;
		for(pli it: adj[u]){
			ll w = it.first; int v = it.second;
			if(D[u] < inf && D[u] + w < D[v]) pq.emplace(D[v] = D[u] + w, v);
		}
	}
	for(int i = 0; i<m; ++i){
		int u, v, _; tie(u, v, _) = E[i];
		edges[i] = make_tuple(min(D[u], D[v]), u, v);
	}
	for(int i = 0; i<n; ++i){
		adj[i].clear(); p[i] = i; sz[i] = 1; fill(mn[i], mn[i]+LOG, inf);
	}
	sort(edges, edges+m, greater<tuple<ll,int,int>>());
	for(int i = 0; i<m; ++i){
		ll w; int u, v; tie(w, u, v) = edges[i];
		if(fp(u) != fp(v)){
			int pu = fp(u), pv = fp(v);
			if(sz[pu] < sz[pv]) swap(pu, pv);
			sz[pu] += sz[pv]; p[pv] = pu;
			adj[u].emplace_back(w, v); adj[v].emplace_back(w, u);
		}
	}
	dfs(0, 0, inf);
	int q; scanf("%d", &q);
	while(q--){
		int u, v; scanf("%d %d", &u, &v); --u; --v;
		pair<ll,int> tmp = get_lca(u, v);
		ll w = tmp.first; int lca = tmp.second;
		printf("%lld\n", w);
	}
}	

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

plan.cpp: In function 'int main()':
plan.cpp:48:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |   if(vis[u]) continue; vis[u] = true;
      |   ^~
plan.cpp:48:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |   if(vis[u]) continue; vis[u] = true;
      |                        ^~~
plan.cpp:76:25: warning: unused variable 'lca' [-Wunused-variable]
   76 |   ll w = tmp.first; int lca = tmp.second;
      |                         ^~~
plan.cpp:36:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  int n, m; scanf("%d %d", &n, &m); LOG = 32 - __builtin_clz(n);
      |            ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d %d %d", &u, &v, &w); --u; --v;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  int k; scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~
plan.cpp:45:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  for(int i = 0, u; i<k; ++i) scanf("%d", &u), pq.emplace(D[u-1] = 0, u-1);
      |                              ~~~~~^~~~~~~~~~
plan.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
plan.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   int u, v; scanf("%d %d", &u, &v); --u; --v;
      |             ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46