結果
問題 | No.1153 ねこちゃんゲーム |
ユーザー |
![]() |
提出日時 | 2020-08-08 01:41:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 593 ms / 2,500 ms |
コード長 | 3,344 bytes |
コンパイル時間 | 2,773 ms |
コンパイル使用メモリ | 210,220 KB |
最終ジャッジ日時 | 2025-01-12 18:44:19 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; template <class T> using V = vector<T>; template <class T> using VV = V<V<T>>; #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define rep(i, n) rep2(i, 0, n) #define rep2(i, m, n) for (int i = m; i < (n); i++) #define per(i, b) per2(i, 0, b) #define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--) #define ALL(c) (c).begin(), (c).end() #define SZ(x) ((int)(x).size()) constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); } template <class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; } template <class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; } template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "(" << p.first << "," << p.second << ")"; return os; } template <class T> ostream& operator<<(ostream& os, const vector<T>& v) { os << "{"; rep(i, v.size()) { if (i) os << ","; os << v[i]; } os << "}"; return os; } #ifdef LOCAL void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...); } #define debug(...) \ cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif VV<int> _g, g; V<int> dgr, gr; VV<int> cnt; void dfs(int v, int p) { for (int to : _g[v]) { if (to != p) { dfs(to, v); g[v].pb(to); } } cnt[v].resize(g[v].size() + 5); for (int to : g[v]) cnt[v][dgr[to]]++; dgr[v] = 0; while (cnt[v][dgr[v]]) dgr[v]++; } V<map<int, int>> toc; void calc(int v, int px) { gr[v] = dgr[v]; if (px < cnt[v].size()) cnt[v][px]++; while (cnt[v][gr[v]]) gr[v]++; for (int to : g[v]) { int nx = gr[v]; if (dgr[to] < gr[v] && cnt[v][dgr[to]] == 1) { nx = dgr[to]; } toc[v][to] = nx; calc(to, nx); } } int main() { int N, M; cin >> N >> M; V<int> A(M); rep(i, M) cin >> A[i], --A[i]; _g.resize(N); g.resize(N); gr.resize(N); dgr.resize(N); cnt.resize(N); toc.resize(N); rep(i, N - 1) { int a, b; cin >> a >> b; --a, --b; _g[a].pb(b); _g[b].pb(a); } dfs(0, -1); calc(0, -1); int xo = 0; for (int v : A) xo ^= gr[v]; debug(dgr, gr, xo); if (xo == 0) { cout << "-1 -1" << endl; } else { V<bool> vis(N); rep(i, M) { int v = A[i]; if (vis[v]) continue; vis[v] = 1; for (int to : _g[v]) { if (toc[v].count(to)) { if ((xo ^ gr[v] ^ dgr[to]) == 0) { cout << i + 1 << ' ' << to + 1 << endl; return 0; } } else { if ((xo ^ gr[v] ^ toc[to][v]) == 0) { cout << i + 1 << ' ' << to + 1 << endl; return 0; } } } } } return 0; }