Submission #535477

#TimeUsernameProblemLanguageResultExecution timeMemory
535477AsymmetryMousetrap (CEOI17_mousetrap)C++17
25 / 100
901 ms66152 KiB
//Autor: Bartłomiej Czarkowski #include <bits/stdc++.h> using namespace std; #ifdef DEBUG template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';} template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';} #define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n' #else #define debug(...) {} #endif const int N = 1001000; int n, a, b, m, q; int par[N]; int son[N]; int cost[N]; int blk[N]; int dp[N]; // ile żeby uwięzić i wyprowadzić do ojca vector<int> v[N]; void dfs_dp(int x) { vector<int> war = {0, 0}; for (int i : v[x]) { if (i == par[x]) { continue; } par[i] = x; dfs_dp(i); war.push_back(dp[i]); } nth_element(war.begin(), war.begin() + 1, war.end(), [&](int a, int b) { return a > b; }); dp[x] = war[1] + war.size() - 2; } int main() { scanf("%d%d%d", &n, &q, &m); for (int i = 1; i < n; ++i) { scanf("%d%d", &a, &b); v[a].push_back(b); v[b].push_back(a); } dfs_dp(q); int x = m; while (x != q) { son[par[x]] = x; x = par[x]; } cost[x] = 0; while (x != m) { x = son[x]; vector<int> war = {0, 0}; for (int i : v[x]) { if (i != par[x] && i != son[x]) { war.push_back(dp[i]); } } blk[x] = blk[par[x]] + war.size() - 2; nth_element(war.begin(), war.begin() + 1, war.end(), [&](int a, int b) { return a > b; }); if (war[0] + blk[x] <= cost[par[x]]) { cost[x] = cost[par[x]]; } else { cost[x] = max(war[1] + blk[x], cost[par[x]]); } } //~ for (int i = 1; i <= n; ++i) { //~ printf("%d: %d\n", i, dp[i]); //~ } printf("%d\n", cost[m]); return 0; }

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d%d", &n, &q, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   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...