Submission #1594136
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll = long long; ll top(ll val) { return 1ll << (63ll - __builtin_clzll(val)); } void biin(vector<ll>& w, ll a) { for (auto v : w) if (top(v) & a) a ^= v; if (!a) return; ll t = top(a); for (auto& v : w) if (t & v) v ^= a; w.push_back(a); } vector<ll> biba(vector<ll>& w) { vector<ll> res; for (auto v : w) biin(res, v); return res; } struct Edge { int from, to; ll cost; Edge(int f, int t, ll c) : from(f), to(t), cost(c) {} }; using Edges = vector<Edge>; using Graph = vector<Edges>; vector<ll> cy; int used[100000]; ll d[100000]; void dfs(int v, Graph& G) { used[v] = 1; for (auto& e : G[v]) { if (used[e.to]) cy.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, f, t, a, b; ll p; cin >> N >> M >> Q; Graph G(N); for (int i = 0; i < M; i++) { cin >> f >> t >> p; G[f].emplace_back(f, t, p); G[t].emplace_back(t, f, p); } dfs(0, G); auto bit = biba(cy); sort(bit.rbegin(), bit.rend()); while (Q--) { cin >> a >> b; ll res = d[a] ^ d[b]; for (auto& v : bit) if (res & ~top(v)) 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 | 1290 Byte |
Status | WA |
Exec Time | 188 ms |
Memory | 18040 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 | WA | 1 ms | 256 KB |
0_01_Teuchi_01 | AC | 1 ms | 256 KB |
0_10_PerfectRandom_00_000004_000004 | WA | 1 ms | 256 KB |
0_10_PerfectRandom_01_000005_000007 | WA | 1 ms | 256 KB |
0_10_PerfectRandom_02_000009_000013 | WA | 1 ms | 256 KB |
0_21_Star_02_000009_000008 | AC | 1 ms | 256 KB |
0_21_Star_03_000012_000011 | AC | 1 ms | 256 KB |
0_22_BinaryTree_01_000005_000004 | AC | 1 ms | 256 KB |
0_23_RandomTree_00_000004_000003 | AC | 1 ms | 256 KB |
0_25_Ring_00_000003_000003 | AC | 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 | AC | 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 | AC | 1 ms | 256 KB |
0_30_Island_01_000007_000006 | AC | 1 ms | 256 KB |
0_30_Island_02_000009_000008 | AC | 1 ms | 256 KB |
0_40_Corner_00_000010_000020 | WA | 27 ms | 1920 KB |
0_40_Corner_01_000021_000020 | AC | 26 ms | 2048 KB |
1_01_Teuchi_00 | AC | 5 ms | 1920 KB |
1_10_PerfectRandom_03_000013_000021 | WA | 1 ms | 256 KB |
1_10_PerfectRandom_04_000021_000106 | WA | 1 ms | 256 KB |
1_10_PerfectRandom_05_000029_000210 | WA | 1 ms | 256 KB |
1_10_PerfectRandom_06_000236_007490 | WA | 5 ms | 896 KB |
1_10_PerfectRandom_07_000843_061761 | WA | 31 ms | 5124 KB |
1_10_PerfectRandom_08_004086_126064 | WA | 67 ms | 9340 KB |
1_10_PerfectRandom_09_007303_126754 | WA | 68 ms | 10100 KB |
1_10_PerfectRandom_10_064317_081046 | WA | 63 ms | 9592 KB |
1_10_PerfectRandom_11_069565_075242 | WA | 60 ms | 8824 KB |
1_20_Line_08_003103_003102 | AC | 4 ms | 896 KB |
1_20_Line_09_002580_002579 | AC | 3 ms | 768 KB |
1_20_Line_10_069209_069208 | AC | 62 ms | 12536 KB |
1_22_BinaryTree_06_000398_000397 | AC | 1 ms | 384 KB |
1_23_RandomTree_05_000060_000059 | AC | 1 ms | 256 KB |
1_24_SkewTree_04_000069_000068 | AC | 1 ms | 256 KB |
1_24_SkewTree_07_000796_000795 | AC | 2 ms | 384 KB |
1_24_SkewTree_11_098814_098813 | AC | 86 ms | 11768 KB |
1_25_Ring_02_001000_001000 | WA | 2 ms | 512 KB |
1_25_Ring_03_100000_100000 | WA | 93 ms | 18040 KB |
1_26_Complete_02_000067_002211 | WA | 2 ms | 512 KB |
1_26_Complete_03_000500_124750 | WA | 127 ms | 6900 KB |
1_27_Random_02_000008_000022 | WA | 1 ms | 256 KB |
1_27_Random_04_000039_000581 | WA | 1 ms | 384 KB |
1_27_Random_05_000050_000407 | WA | 1 ms | 256 KB |
1_27_Random_06_000307_020347 | WA | 12 ms | 2044 KB |
1_27_Random_07_000551_065255 | WA | 24 ms | 4088 KB |
1_27_Random_08_006629_062527 | AC | 29 ms | 5368 KB |
1_27_Random_09_009865_050301 | WA | 34 ms | 4860 KB |
1_27_Random_10_042323_075720 | AC | 55 ms | 8948 KB |
1_27_Random_11_043628_107061 | WA | 101 ms | 11508 KB |
1_30_Island_03_000013_000063 | AC | 1 ms | 256 KB |
1_30_Island_04_000094_000093 | AC | 1 ms | 256 KB |
1_30_Island_05_000039_000038 | AC | 1 ms | 256 KB |
1_30_Island_06_000364_000363 | AC | 1 ms | 384 KB |
1_30_Island_07_000951_000952 | WA | 2 ms | 384 KB |
1_30_Island_08_005937_005936 | AC | 5 ms | 1024 KB |
1_30_Island_09_008024_008090 | WA | 9 ms | 1280 KB |
1_30_Island_10_011040_047244 | WA | 42 ms | 4216 KB |
1_30_Island_11_046719_053967 | WA | 45 ms | 6268 KB |
1_30_Island_12_099995_164170 | WA | 188 ms | 15856 KB |
1_30_Island_13_099996_159191 | WA | 183 ms | 15600 KB |
1_30_Island_14_099992_157444 | WA | 183 ms | 15476 KB |