제출 #713024

#제출 시각아이디문제언어결과실행 시간메모리
713024stevancvTorrent (COI16_torrent)C++14
100 / 100
462 ms31224 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 3e5 + 2; const int inf = 1e9; vector<pair<int, int>> g[N]; int par[N]; void Dfs(int s, int e) { for (auto u : g[s]) { if (u.first == e) continue; par[u.first] = u.second; Dfs(u.first, s); } } int Dfs1(int s, int e, int c) { vector<int> all; for (auto u : g[s]) { if (u.first == e || u.second == c) continue; all.push_back(Dfs1(u.first, s, c)); } sort(all.rbegin(), all.rend()); int o = 0; for (int i = 0; i < all.size(); i++) { smax(o, all[i] + i + 1); } return o; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, a, b; cin >> n >> a >> b; vector<int> u(n - 1), v(n - 1); for (int i = 0; i < n - 1; i++) { cin >> u[i] >> v[i]; g[u[i]].push_back({v[i], i}); g[v[i]].push_back({u[i], i}); par[i] = -1; } Dfs(a, 0); for (int i = 0; i < n - 1; i++) { if (par[v[i]] != i) swap(u[i], v[i]); } vector<int> p; int x = b; while (x != a) { p.push_back(par[x]); x = u[par[x]]; } int sz = p.size(); if (a == b) { cout << Dfs1(a, 0, -1) << en; return 0; } int l = 0, r = sz - 1, ans = sz - 1; while (l <= r) { int mid = l + r >> 1; int c = p[mid]; if (Dfs1(a, 0, c) >= Dfs1(b, 0, c)) { l = mid + 1; ans = mid; } else r = mid - 1; } int sol = Dfs1(a, 0, p[ans]); if (ans < sz - 1) smin(sol, Dfs1(b, 0, p[ans + 1])); cout << sol << en; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

torrent.cpp: In function 'int Dfs1(int, int, int)':
torrent.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < all.size(); i++) {
      |                     ~~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid = l + r >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...