結果
問題 | No.1153 ねこちゃんゲーム |
ユーザー |
👑 ![]() |
提出日時 | 2020-08-07 22:14:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 513 ms / 2,500 ms |
コード長 | 2,420 bytes |
コンパイル時間 | 3,219 ms |
コンパイル使用メモリ | 220,432 KB |
最終ジャッジ日時 | 2025-01-12 17:05:14 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // const int MOD = 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); } } iosetup; int main() { int n, m; cin >> n >> m; vector<int> a(m); REP(i, m) cin >> a[i], --a[i]; vector<vector<int>> graph(n); REP(_, n - 1) { int u, v; cin >> u >> v; --u; --v; graph[u].emplace_back(v); graph[v].emplace_back(u); } vector<vector<pair<int, int>>> chi(n); function<int(int, int)> pre = [&](int par, int ver) { set<int> st; for (int e : graph[ver]) { if (e == par) continue; int d = pre(ver, e); st.emplace(d); chi[ver].emplace_back(d, e); } int res = 0; while (st.count(res) == 1) ++res; return res; }; pre(-1, 0); vector<int> gru(n); function<void(int, int, int)> dfs = [&](int par, int ver, int par_val) { if (par_val >= 0) chi[ver].emplace_back(par_val, par); map<int, vector<int>> mp; for (auto [val, dst] : chi[ver]) mp[val].emplace_back(dst); map<int, int> children; gru[ver] = 0; while (mp.count(gru[ver]) == 1) { if (mp[gru[ver]].size() == 1) children[mp[gru[ver]][0]] = gru[ver]; ++gru[ver]; } for (int e : graph[ver]) { if (e != par) dfs(ver, e, children.count(e) == 1 ? children[e] : gru[ver]); } }; dfs(-1, 0, -1); int x = 0; REP(i, m) x ^= gru[a[i]]; if (x > 0) { vector visited(n, false); REP(i, m) { if (visited[a[i]]) continue; visited[a[i]] = true; for (auto [val, dst] : chi[a[i]]) { if ((x ^ gru[a[i]] ^ val) == 0) { cout << i + 1 << ' ' << dst + 1 << '\n'; return 0; } } } assert(false); } cout << "-1 -1\n"; return 0; }