Submission #31989

#TimeUsernameProblemLanguageResultExecution timeMemory
31989cki86201오두막집 (GA7_cabana)C++11
0 / 100
3 ms5700 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <queue> #include <map> #include <set> #include <string> #include <algorithm> #include <iostream> #include <functional> #include <unordered_map> #include <unordered_set> #include <list> #include <bitset> using namespace std; typedef pair<int, int> pii; typedef long long ll; #define Fi first #define Se second #define pb(x) push_back(x) #define sz(x) ((int)(x).size()) #define rep(i, n) for(int i=0;i<n;i++) #define all(x) (x).begin(), (x).end() typedef tuple<int, int, int> t3; typedef pair<ll, ll> pll; typedef long double ldouble; typedef pair<double, double> pdd; int N, M; ll K; vector <pii> E[100010]; int C[100010]; int down[100010]; int cut[100010]; void pdfs(int x, int fa) { down[x] = 1; for(pii e : E[x]) if(e.Se != fa && cut[e.Se] == 0) { pdfs(e.Se, x); down[x] += down[e.Se]; } } void dfs(int x, int fa, int L, vector <int> &v) { if(C[x]) v.pb(L); for(pii e : E[x]) if(e.Se != fa && cut[e.Se] == 0) { dfs(e.Se, x, L + e.Fi, v); } } ll Get(vector <vector <int> > &X, int L) { priority_queue <pii, vector<pii>, greater<pii> > pq; int n = sz(X); rep(i, n) pq.push(pii(sz(X[i]), i)); ll res = 0; X.resize(n+n-1); int now = n; while(sz(pq) > 1) { pii a = pq.top(); pq.pop(); pii b = pq.top(); pq.pop(); int ia = a.Se, ib = b.Se; int La = sz(X[ia]), Lb = sz(X[ib]); vector <int> R(La + Lb); for(int a=La-1, b=0;a>=0;a--) { while(b < Lb && X[ia][a] + X[ib][b] <= L) ++b; res += b; } for(int a=0, b=0, c=0;c<La + Lb;c++) { if(a == La || (b < Lb && X[ib][b] <= X[ia][a])) R[c] = X[ib][b++]; else R[c] = X[ia][a++]; } X[now] = R; pq.push(pii(a.Fi + b.Fi, now)); ++now; } return res; } ll Do(int x, int L) { pdfs(x, -1); int h = down[x] / 2; while(1) { int f = 0; for(pii e : E[x]) if(down[x] > down[e.Se] && down[e.Se] > h) { x = e.Se; f = 1; break; } if(f == 0) break; } vector <vector <int> > P; if(C[x] == 1) { vector <int> v; v.pb(0); P.pb(v); } cut[x] = 1; for(pii e : E[x]) if(cut[e.Se] == 0) { vector <int> v; dfs(e.Se, x, e.Fi, v); sort(all(v)); if(sz(v)) P.pb(v); } ll res = Get(P, L); for(pii e : E[x]) if(cut[e.Se] == 0) res += Do(e.Se, L); return res; } ll Get(int L) { memset(cut, 0, sizeof cut); return Do(1, L); } void solve(){ scanf("%d%d%lld", &N, &M, &K); for(int i=2;i<=N;i++) { int x, y; scanf("%d%d", &x, &y); E[i].pb(pii(y, x)); E[x].pb(pii(y, i)); } rep(i, M) { int x; scanf("%d", &x); C[x] = 1; } int low = 1, high = (N-1) * 250, res = -1; while(low <= high) { int mid = (low + high) >> 1; if(Get(mid) >= K) res = mid, high = mid - 1; else low = mid + 1; } printf("%d\n", res); } int main(){ int Tc = 1; // scanf("%d\n", &Tc); for(int tc=1;tc<=Tc;tc++){ //printf("Case #%d\n", tc); solve(); } return 0; };

Compilation message (stderr)

cabana.cpp: In function 'void solve()':
cabana.cpp:116: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:118:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^
cabana.cpp:123:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; 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...