Submission #31994

#TimeUsernameProblemLanguageResultExecution timeMemory
31994kazel오두막집 (GA7_cabana)C++14
0 / 100
133 ms5476 KiB
#include<bits/stdc++.h> using namespace std; struct edge { int t, w; edge(int t, int w) : t(t), w(w) {} }; vector<edge> g[100005]; bool b[100005], v[100005]; int cnt[100005], cb[100005]; long long k; vector<int> ord; void init(int c, int p) { cnt[c] = 1; cb[c] += b[c]; for(auto e : g[c]) { if(e.t == p) continue; init(e.t,c); cnt[c] += cnt[e.t]; cb[c] += cb[e.t]; } } int center(int c) { int n = cnt[c], m = cb[c]; int mxi = g[c][0].t; for(auto e : g[c]) { if(v[e.t]) continue; if(cnt[e.t] > cnt[mxi]) mxi = e.t; } if(cnt[mxi]>n/2) { cnt[c] = n - cnt[mxi]; cb[c] = m - cb[mxi]; cnt[mxi] = n; cb[mxi] = m; return center(mxi); } return c; } void dfs(int c, int p, int w, map<int,int> & mp) { if(b[c]) mp[w]++; for(auto e : g[c]) { if(e.t == p) continue; dfs(e.t,c,w+e.w,mp); } } long long foo(int d) { long long ret = 0; memset(v,0,sizeof(v)); for(int i : ord) { v[i] = true; map<int,int> pr; if(b[i]) pr[0] = 1; for(auto e : g[i]) { if(v[e.t]) continue; map<int,int> cu; dfs(e.t,i,e.w,cu); for(auto p : pr) { int a = p.first; long long b = p.second; for(auto q : cu) { if(a+q.first > d) break; ret += b * q.second; if(ret > k) return ret; } } for(auto p : cu) { if(p.first>=d) break; pr[p.first] += p.second; } } } return ret; } int main() { int n,m,l=1,r=0; scanf("%d%d%lld",&n,&m,&k); for(int i=2;i<=n;i++) { int a,w; scanf("%d%d",&a,&w); g[i].push_back(edge(a,w)); g[a].push_back(edge(i,w)); r += w; } for(int i=0;i<m;i++) { int x; scanf("%d",&x); b[x] = true; } init(1,0); queue<int> q; q.push(1); while(!q.empty()) { int r = q.front(); q.pop(); if(cb[r]<2) continue; r = center(r); ord.push_back(r); v[r] = true; for(auto e : g[r]) { if(v[e.t]) continue; q.push(e.t); } } int ans = r--; while(r>=l) { int c = (l+r)/2; if(foo(c)>=k) { ans = c; r = c - 1; } else l = c + 1; } printf("%d\n",ans); }

Compilation message (stderr)

cabana.cpp: In function 'int main()':
cabana.cpp:98:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%lld",&n,&m,&k);
                               ^
cabana.cpp:102:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&w);
                            ^
cabana.cpp:110:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
#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...