結果
問題 | No.2532 Want Play More |
ユーザー |
|
提出日時 | 2023-11-03 23:29:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 270 ms / 2,000 ms |
コード長 | 931 bytes |
コンパイル時間 | 2,278 ms |
コンパイル使用メモリ | 205,284 KB |
最終ジャッジ日時 | 2025-02-17 18:56:25 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main () {int N;cin >> N;std::vector<int> tr[200020];for (int i = 1; i < N; i ++) {int a, b;cin >> a >> b;tr[--a].push_back(--b);tr[b].push_back(a);}vector<int> D(N, -1);D[0] = 0;queue<int> que;que.push(0);while (!que.empty()) {int u = que.front();que.pop();for (auto v : tr[u]) {if (D[v] == -1) {D[v] = D[u] + 1;que.push(v);}}}int dp[200020][2];vector<int> ID(N);iota(ID.begin(), ID.end(), 0);sort(ID.begin(), ID.end(), [&](int a, int b) {return D[a] > D[b];});for (auto u : ID) {dp[u][0] = 0;for (auto v : tr[u]) {if (D[v] < D[u]) continue;dp[u][0] = max(dp[u][0], dp[v][1] + 1);}dp[u][1] = N + 10;for (auto v : tr[u]) {if (D[v] < D[u]) continue;dp[u][1] = min(dp[u][1], dp[v][0] + 1);}if (dp[u][1] > N) dp[u][1] = 0;}cout << dp[0][0] << "\n" << dp[0][1] << endl;}