Submission #1594092
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll = long long; struct Edge { int from, to; ll cost; Edge() {} Edge(int f, int t, int c) : from(f), to(t), cost(c) {} }; using Edges = vector<Edge>; using Graph = vector<Edges>; vector<ll> cycles; int used[100000]; int d[100000]; ll top(ll val) { while (val & (val - 1)) val = val & (val - 1); return val; } void binary_basis_insert(vector<ll>& w, ll a) { for (auto v : w) { ll t = top(v); if (t & a) a ^= v; } if (a == 0) return; ll t = top(a); for (auto& v : w) if (t & v) v ^= a; w.push_back(a); } vector<ll> binary_basis(const vector<ll>& w) { vector<ll> res; for (auto v : w) { binary_basis_insert(res, v); } return res; } void dfs(int v, const Graph& G) { used[v] = 1; for (auto e : G[v]) { if (used[e.to]) { cycles.push_back(d[v] ^ d[e.to] ^ e.cost); } else { d[e.to] = d[v] ^ e.cost; dfs(e.to, G); } } } int main() { ios::sync_with_stdio(false), cin.tie(0); int N, M, Q; cin >> N >> M >> Q; Graph G(N); for (int i = 0; i < M; i++) { int f, t; ll p; cin >> f >> t >> p; G[f].emplace_back(f, t, p); G[t].emplace_back(t, f, p); } dfs(0, G); auto bit = binary_basis(cycles); sort(bit.rbegin(), bit.rend()); while (Q--) { int a, b; cin >> a >> b; ll res = d[a] ^ d[b]; for (auto v : bit) { ll t = top(v); if (!(res & t)) { res ^= v; } } printf("%lld\n", res); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | K - XOR回廊 |
User | kazuma |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1515 Byte |
Status | WA |
Exec Time | 149 ms |
Memory | 16888 KB |
Judge Result
Set Name | Partial 1 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 60 | 0 / 140 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Partial 1 | 0_00_sample_00, 0_01_Teuchi_01, 0_10_PerfectRandom_00_000004_000004, 0_10_PerfectRandom_01_000005_000007, 0_10_PerfectRandom_02_000009_000013, 0_21_Star_02_000009_000008, 0_21_Star_03_000012_000011, 0_22_BinaryTree_01_000005_000004, 0_23_RandomTree_00_000004_000003, 0_25_Ring_00_000003_000003, 0_25_Ring_01_000020_000020, 0_26_Complete_00_000004_000006, 0_26_Complete_01_000005_000010, 0_27_Random_00_000002_000001, 0_27_Random_01_000005_000010, 0_27_Random_03_000013_000013, 0_30_Island_00_000004_000004, 0_30_Island_01_000007_000006, 0_30_Island_02_000009_000008, 0_40_Corner_00_000010_000020, 0_40_Corner_01_000021_000020 |
All | 0_00_sample_00, 0_01_Teuchi_01, 0_10_PerfectRandom_00_000004_000004, 0_10_PerfectRandom_01_000005_000007, 0_10_PerfectRandom_02_000009_000013, 0_21_Star_02_000009_000008, 0_21_Star_03_000012_000011, 0_22_BinaryTree_01_000005_000004, 0_23_RandomTree_00_000004_000003, 0_25_Ring_00_000003_000003, 0_25_Ring_01_000020_000020, 0_26_Complete_00_000004_000006, 0_26_Complete_01_000005_000010, 0_27_Random_00_000002_000001, 0_27_Random_01_000005_000010, 0_27_Random_03_000013_000013, 0_30_Island_00_000004_000004, 0_30_Island_01_000007_000006, 0_30_Island_02_000009_000008, 0_40_Corner_00_000010_000020, 0_40_Corner_01_000021_000020, 1_01_Teuchi_00, 1_10_PerfectRandom_03_000013_000021, 1_10_PerfectRandom_04_000021_000106, 1_10_PerfectRandom_05_000029_000210, 1_10_PerfectRandom_06_000236_007490, 1_10_PerfectRandom_07_000843_061761, 1_10_PerfectRandom_08_004086_126064, 1_10_PerfectRandom_09_007303_126754, 1_10_PerfectRandom_10_064317_081046, 1_10_PerfectRandom_11_069565_075242, 1_20_Line_08_003103_003102, 1_20_Line_09_002580_002579, 1_20_Line_10_069209_069208, 1_22_BinaryTree_06_000398_000397, 1_23_RandomTree_05_000060_000059, 1_24_SkewTree_04_000069_000068, 1_24_SkewTree_07_000796_000795, 1_24_SkewTree_11_098814_098813, 1_25_Ring_02_001000_001000, 1_25_Ring_03_100000_100000, 1_26_Complete_02_000067_002211, 1_26_Complete_03_000500_124750, 1_27_Random_02_000008_000022, 1_27_Random_04_000039_000581, 1_27_Random_05_000050_000407, 1_27_Random_06_000307_020347, 1_27_Random_07_000551_065255, 1_27_Random_08_006629_062527, 1_27_Random_09_009865_050301, 1_27_Random_10_042323_075720, 1_27_Random_11_043628_107061, 1_30_Island_03_000013_000063, 1_30_Island_04_000094_000093, 1_30_Island_05_000039_000038, 1_30_Island_06_000364_000363, 1_30_Island_07_000951_000952, 1_30_Island_08_005937_005936, 1_30_Island_09_008024_008090, 1_30_Island_10_011040_047244, 1_30_Island_11_046719_053967, 1_30_Island_12_099995_164170, 1_30_Island_13_099996_159191, 1_30_Island_14_099992_157444 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00_sample_00 | AC | 1 ms | 256 KB |
0_01_Teuchi_01 | AC | 1 ms | 256 KB |
0_10_PerfectRandom_00_000004_000004 | AC | 1 ms | 256 KB |
0_10_PerfectRandom_01_000005_000007 | AC | 1 ms | 256 KB |
0_10_PerfectRandom_02_000009_000013 | AC | 1 ms | 256 KB |
0_21_Star_02_000009_000008 | WA | 1 ms | 256 KB |
0_21_Star_03_000012_000011 | WA | 1 ms | 256 KB |
0_22_BinaryTree_01_000005_000004 | WA | 1 ms | 256 KB |
0_23_RandomTree_00_000004_000003 | WA | 1 ms | 256 KB |
0_25_Ring_00_000003_000003 | WA | 1 ms | 256 KB |
0_25_Ring_01_000020_000020 | WA | 1 ms | 256 KB |
0_26_Complete_00_000004_000006 | WA | 1 ms | 256 KB |
0_26_Complete_01_000005_000010 | WA | 1 ms | 256 KB |
0_27_Random_00_000002_000001 | WA | 1 ms | 256 KB |
0_27_Random_01_000005_000010 | WA | 1 ms | 256 KB |
0_27_Random_03_000013_000013 | WA | 1 ms | 256 KB |
0_30_Island_00_000004_000004 | WA | 1 ms | 256 KB |
0_30_Island_01_000007_000006 | WA | 1 ms | 256 KB |
0_30_Island_02_000009_000008 | WA | 1 ms | 256 KB |
0_40_Corner_00_000010_000020 | WA | 31 ms | 1408 KB |
0_40_Corner_01_000021_000020 | WA | 25 ms | 1280 KB |
1_01_Teuchi_00 | AC | 5 ms | 1920 KB |
1_10_PerfectRandom_03_000013_000021 | AC | 1 ms | 256 KB |
1_10_PerfectRandom_04_000021_000106 | AC | 1 ms | 256 KB |
1_10_PerfectRandom_05_000029_000210 | AC | 1 ms | 256 KB |
1_10_PerfectRandom_06_000236_007490 | AC | 5 ms | 896 KB |
1_10_PerfectRandom_07_000843_061761 | AC | 30 ms | 5124 KB |
1_10_PerfectRandom_08_004086_126064 | AC | 65 ms | 9340 KB |
1_10_PerfectRandom_09_007303_126754 | AC | 67 ms | 10100 KB |
1_10_PerfectRandom_10_064317_081046 | AC | 64 ms | 9336 KB |
1_10_PerfectRandom_11_069565_075242 | AC | 61 ms | 8568 KB |
1_20_Line_08_003103_003102 | WA | 4 ms | 768 KB |
1_20_Line_09_002580_002579 | WA | 3 ms | 768 KB |
1_20_Line_10_069209_069208 | WA | 62 ms | 11640 KB |
1_22_BinaryTree_06_000398_000397 | WA | 1 ms | 384 KB |
1_23_RandomTree_05_000060_000059 | WA | 1 ms | 256 KB |
1_24_SkewTree_04_000069_000068 | WA | 1 ms | 256 KB |
1_24_SkewTree_07_000796_000795 | WA | 2 ms | 384 KB |
1_24_SkewTree_11_098814_098813 | WA | 84 ms | 10616 KB |
1_25_Ring_02_001000_001000 | WA | 2 ms | 512 KB |
1_25_Ring_03_100000_100000 | WA | 91 ms | 16888 KB |
1_26_Complete_02_000067_002211 | WA | 2 ms | 512 KB |
1_26_Complete_03_000500_124750 | WA | 83 ms | 6900 KB |
1_27_Random_02_000008_000022 | WA | 1 ms | 256 KB |
1_27_Random_04_000039_000581 | WA | 2 ms | 384 KB |
1_27_Random_05_000050_000407 | WA | 1 ms | 256 KB |
1_27_Random_06_000307_020347 | WA | 15 ms | 2172 KB |
1_27_Random_07_000551_065255 | WA | 25 ms | 4088 KB |
1_27_Random_08_006629_062527 | WA | 29 ms | 5240 KB |
1_27_Random_09_009865_050301 | WA | 41 ms | 4860 KB |
1_27_Random_10_042323_075720 | WA | 55 ms | 8564 KB |
1_27_Random_11_043628_107061 | WA | 100 ms | 11256 KB |
1_30_Island_03_000013_000063 | WA | 1 ms | 256 KB |
1_30_Island_04_000094_000093 | WA | 1 ms | 256 KB |
1_30_Island_05_000039_000038 | WA | 1 ms | 256 KB |
1_30_Island_06_000364_000363 | WA | 1 ms | 384 KB |
1_30_Island_07_000951_000952 | WA | 2 ms | 384 KB |
1_30_Island_08_005937_005936 | WA | 5 ms | 896 KB |
1_30_Island_09_008024_008090 | WA | 8 ms | 1280 KB |
1_30_Island_10_011040_047244 | WA | 37 ms | 4088 KB |
1_30_Island_11_046719_053967 | WA | 44 ms | 5628 KB |
1_30_Island_12_099995_164170 | WA | 148 ms | 14704 KB |
1_30_Island_13_099996_159191 | WA | 149 ms | 14320 KB |
1_30_Island_14_099992_157444 | WA | 148 ms | 14324 KB |