Submission #196891

#TimeUsernameProblemLanguageResultExecution timeMemory
196891arnold518Valley (BOI19_valley)C++14
0 / 100
236 ms28564 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; const int INF = 987654321; struct Edge { int u, v, w; }; int N, S, Q, E; vector<pii> adj[MAXN+10]; Edge edge[MAXN+10]; int C[MAXN+10]; int L[MAXN+10], R[MAXN+10], pos[MAXN+10], cnt; bool reach(int I, int u, int v) { bool a=(L[edge[I].v]<=L[u] && L[u]<=R[edge[I].v]); bool b=(L[edge[I].v]<=L[v] && L[v]<=R[edge[I].v]); return a==b; } void dfs(int now, int bef) { L[now]=R[now]=++cnt; pos[L[now]]=now; for(auto nxt : adj[now]) { if(nxt.first==bef) continue; dfs(nxt.first, now); R[now]=max(R[now], R[nxt.first]); } } int sz[MAXN+10], cenpar[MAXN+10], dist[MAXN+10][30], cendep[MAXN+10]; pii D1[MAXN+10], D2[MAXN+10]; bool del[MAXN+10]; void getsz(int now, int bef) { sz[now]=1; for(auto nxt : adj[now]) { if(nxt.first==bef) continue; if(del[nxt.first]) continue; getsz(nxt.first, now); sz[now]+=sz[nxt.first]; } } int getcen(int now, int bef, int S) { for(auto nxt : adj[now]) { if(nxt.first==bef) continue; if(del[nxt.first]) continue; if(sz[nxt.first]>S/2) return getcen(nxt.first, now, S); } return now; } pii dfs2(int now, int bef, int depth, int root, int cdep) { dist[now][cdep]=depth; pii ret={INF, INF}; if(C[now]) ret=min(ret, {depth, root}); for(auto nxt : adj[now]) { if(nxt.first==bef) continue; if(del[nxt.first]) continue; ret=min(ret, dfs2(nxt.first, now, depth+nxt.second, root, cdep)); } return ret; } int decomp(int now, int bef, int dep) { getsz(now, now); now=getcen(now, now, sz[now]); del[now]=true; cendep[now]=dep; if(bef) cenpar[now]=bef; else cenpar[now]=now; D1[now]={INF, INF}; D2[now]={INF, INF}; for(auto nxt : adj[now]) { if(del[nxt.first]) continue; int nxtcen=decomp(nxt.first, now, dep+1); pii t=dfs2(nxt.first, now, nxt.second, nxtcen, dep); if(t<D1[now]) D2[now]=D1[now], D1[now]=t; else if(t<D2[now]) D2[now]=t; } //printf("%d : %d %d / %d %d\n", now, D1[now].first, D1[now].second, D2[now].first, D2[now].second); del[now]=false; return now; } int query(int now, int cut) { int ans=INF, bef=now, beg=now; while(1) { if(reach(cut, beg, now)) { if(D1[now].second!=bef) ans=min(ans, D1[now].first+dist[beg][cendep[now]]); else ans=min(ans, D2[now].first+dist[beg][cendep[now]]); if(C[now]) ans=min(ans, dist[bef][cendep[now]]); } if(now==cenpar[now]) break; bef=now; now=cenpar[now]; } return ans; } int main() { int i, j; scanf("%d%d%d%d", &N, &S, &Q, &E); for(i=1; i<N; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); adj[u].push_back({v, w}); adj[v].push_back({u, w}); edge[i]={u, v, w}; } for(i=1; i<=S; i++) { int t; scanf("%d", &t); C[t]=1; } dfs(E, E); for(i=1; i<N; i++) if(L[edge[i].u]>L[edge[i].v]) swap(edge[i].u, edge[i].v); decomp(1, 0, 0); while(Q--) { int A, B; scanf("%d%d", &A, &B); if(reach(A, E, B)) { printf("escaped\n"); continue; } int t=query(B, A); if(t==INF) printf("oo\n"); else printf("%d\n", t); } }

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:129:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
valley.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &S, &Q, &E);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
valley.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A, &B);
   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...