Submission #161079

#TimeUsernameProblemLanguageResultExecution timeMemory
161079AkashiMousetrap (CEOI17_mousetrap)C++14
100 / 100
1132 ms158688 KiB
#include <bits/stdc++.h> using namespace std; const int lim = 1e6 + 5; int n, t, m; int w[lim], h[lim], TT[lim]; vector <int> v[lim]; void dfs(int nod = t, int papa = 0){ bool frunza = true; int Max = 0, Max2 = 0; for(auto it : v[nod]){ if(papa == it) continue ; frunza = false; TT[it] = nod; w[it] = w[nod]; h[it] = h[nod] + 1; if(nod != t) w[it] = w[it] + (v[nod].size() - 2); dfs(it, nod); if(w[it] > Max) Max2 = Max, Max = w[it]; else if(w[it] > Max2) Max2 = w[it]; } if(frunza) w[nod] = w[nod] + h[nod]; else{ if(Max2 == 0) w[nod] = w[nod] + h[nod] + 1; else w[nod] = Max2; } } inline bool check(int tmp){ int cnt = 0; for(int nod = m, nr = 0, Last = 0; nod != t ; Last = nod, nod = TT[nod], ++nr){ int aux = 0; for(auto it : v[nod]){ if(it == TT[nod] || it == Last) continue ; if(w[it] - h[nod] - (nod != m) + cnt > tmp) ++aux; } cnt = cnt + aux; if(cnt > nr + 1) return 0; } if(cnt > tmp) return 0; return 1; } int main() { // freopen("1.in", "r", stdin); scanf("%d%d%d", &n, &t, &m); int x, y; for(int i = 2; i <= n ; ++i){ scanf("%d%d", &x, &y); v[x].push_back(y); v[y].push_back(x); } dfs(); int st = 0, dr = 2 * n; while(st <= dr){ int mij = (st + dr) / 2; if(check(mij)) dr = mij - 1; else st = mij + 1; } printf("%d", st); return 0; }

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &t, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...