제출 #474545

#제출 시각아이디문제언어결과실행 시간메모리
474545ThaiBaHungTorrent (COI16_torrent)C++14
69 / 100
641 ms29224 KiB
#include <bits/stdc++.h> using namespace std; const int N = 3e5 + 4; int n, x, y; int socon[3][N]; vector < int > adj[N]; int cha[3][N]; int L[N], R[N]; vector < int > path; bool kt[N]; int dp[N]; void dfs(int i, int j, int id) { socon[id][i] = 1; for (int u : adj[i]) { if (u == j) continue; dfs(u, i, id); cha[id][u] = i; socon[id][i] += socon[id][u]; } } bool cmp(int a, int b) { return dp[a] > dp[b]; } void xuly(int i, int j, int dif) { vector < int > con; for (int u : adj[i]) { if (u == j) continue; if (u == dif) continue; xuly(u, i, dif); con.push_back(u); } if (con.size() == 0) { dp[i] = 1; return; } sort(con.begin(), con.end(), cmp); for (int t = 0; t < con.size(); t++) { dp[i] = max(dp[i], dp[con[t]] + t + 1); // if (i == x) cout << con[t] << " " << dp[con[t]] << '\n'; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("t.inp","r",stdin); freopen("t.out","w",stdout); cin >> n >> x >> y; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); kt[u] = kt[v] = false; } dfs(x, 0, 1); dfs(y, 0, 2); int node = x; while (node != 0) {path.push_back(node); node = cha[2][node];} int lo = 0, hi = path.size() - 2; int res = 1e9 + 7; if (n <= 1000) { for (int i = 0; i < path.size() - 1; i++) { xuly(x, 0, path[i + 1]); xuly(y, 0, path[i]); res = min(res, max(dp[x], dp[y]) - 1); } cout << res; return 0; } // for (int u : path) // cout << u << " "; while (lo <= hi) { int mid = (lo + hi) / 2; //cout << path[mid] << " "; xuly(x, 0, path[mid + 1]); xuly(y, 0, path[mid]); res = min(res, max(dp[x], dp[y]) - 1); //cout << dp[x] << " " << dp[y] << '\n'; if (dp[x] > dp[y]) hi = mid - 1; else lo = mid + 1; } cout << res; }

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

torrent.cpp: In function 'void xuly(int, int, int)':
torrent.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int t = 0; t < con.size(); t++)
      |                     ~~^~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int i = 0; i < path.size() - 1; i++)
      |                         ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...