結果
問題 | No.1790 Subtree Deletion |
ユーザー | 👑 Nachia |
提出日時 | 2021-12-10 20:41:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,007 bytes |
コンパイル時間 | 870 ms |
コンパイル使用メモリ | 86,544 KB |
実行使用メモリ | 12,808 KB |
最終ジャッジ日時 | 2023-10-13 18:17:11 |
合計ジャッジ時間 | 6,796 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
11,364 KB |
testcase_01 | AC | 1 ms
4,352 KB |
testcase_02 | AC | 2 ms
4,352 KB |
testcase_03 | AC | 122 ms
11,956 KB |
testcase_04 | AC | 129 ms
12,808 KB |
testcase_05 | AC | 134 ms
11,868 KB |
testcase_06 | AC | 131 ms
12,540 KB |
testcase_07 | AC | 123 ms
11,860 KB |
testcase_08 | AC | 17 ms
4,348 KB |
testcase_09 | TLE | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(n); i++) struct Edge{ int u,v; u64 a; }; int N; vector<Edge> edges; vector<vector<int>> E; vector<u64> A; vector<int> I; vector<int> depth; vector<int> in_time; vector<int> out_time; void dfs(int p = 0, int pre = -1){ in_time[p] = I.size(); I.push_back(p); for(int e : E[p]) if(e != pre){ depth[e] = depth[p] + 1; dfs(e,p); } out_time[p] = I.size(); } vector<int> erase_visited; void erase_dfs(int p){ if(erase_visited[p]) return; erase_visited[p] = 1; A[p] = 0; for(int e : E[p]) erase_dfs(e); } u64 sum_result = 0; void sum_dfs(int p){ if(erase_visited[p]) return; sum_result ^= A[p]; for(int e : E[p]) sum_dfs(e); } int Q; int main() { cin >> N; edges.resize(N-1); E.resize(N); rep(i,N-1){ int u,v; cin >> u >> v; u--; v--; u64 a; cin >> a; edges[i] = {u,v,a}; E[u].push_back(v); E[v].push_back(u); } depth.assign(N, 0); in_time.assign(N, 0); out_time.assign(N, 0); dfs(); E.clear(); E.resize(N); A.assign(N, 0); for(auto e : edges){ if(depth[e.u] > depth[e.v]) swap(e.u, e.v); A[e.v] = e.a; E[e.u].push_back(e.v); } erase_visited.assign(N, 0); cin >> Q; rep(queryid, Q){ int t; cin >> t; if(t == 1){ int x; cin >> x; x--; erase_dfs(x); } if(t == 2){ int x; cin >> x; x--; int l = in_time[x] + 1; int r = out_time[x]; sum_result = A[x]; sum_dfs(x); cout << sum_result << "\n"; } } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;