Submission #5880637
Source Code Expand
#if 0
cat <<EOF >mistaken-paste
#endif
// thx Ebi-chan!
#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>
#define BIG 2000000007
#define VERYBIG 20000000000000007LL
#define MOD 1000000007
#define FOD 998244353
typedef uint64_t ull;
typedef int64_t sll;
#define N_MAX 1048576
#ifdef __cplusplus
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <functional>
#include <array>
using std::queue;
using std::priority_queue;
using std::stack;
using std::tuple;
using std::set;
using std::map;
using std::vector;
using std::greater;
using std::pair;
using std::string;
using std::get;
template <typename T, typename U>
pair<T, U> operator+(pair<T, U> l, pair<T, U> r) {
return pair<T, U>(l.first + r.first, l.second + r.second);
}
#endif
typedef struct {
sll a;
sll b;
} hwll;
typedef struct {
sll a;
sll b;
sll c;
} hwllc;
typedef struct {
hwll a;
hwll b;
} linell;
typedef struct {
double a;
double b;
} hwreal;
ull n, m;
ull h, w;
ull k;
ull q;
sll va, vb, vc, vd, ve, vf;
ull ua, ub, uc, ud, ue, uf;
long double vra, vrb, vrc;
double vda, vdb, vdc;
char ch, dh;
ull umin (ull x, ull y) {
return (x < y) ? x : y;
}
ull umax (ull x, ull y) {
return (x > y) ? x : y;
}
sll smin (sll x, sll y) {
return (x < y) ? x : y;
}
sll smax (sll x, sll y) {
return (x > y) ? x : y;
}
ull gcd (ull x, ull y) {
if (y == 0) {
return x;
} else {
return gcd(y, x % y);
}
}
ull bitpow (ull a, ull x, ull modulo) {
ull result = 1;
while (x) {
if (x & 1) {
result *= a;
result %= modulo;
}
x /= 2;
a = (a * a) % modulo;
}
return result;
}
ull divide (ull a, ull b, ull modulo) {
return (a * bitpow(b, modulo - 2, modulo)) % modulo;
}
ull udiff (ull a, ull b) {
if (a >= b) {
return a - b;
} else {
return b - a;
}
}
sll sdiff (sll a, sll b) {
if (a >= b) {
return a - b;
} else {
return b - a;
}
}
int bitcount (ull n) {
int result = 0;
while (n) {
if (n & 1) result++;
n /= 2;
}
return result;
}
#define BEGCMP(NAME) int32_t NAME (const void *left, const void *right)
#define DEFLR(TYPE) TYPE l=*(TYPE*)left,r=*(TYPE*)right
#define CMPRET(L, R) if((L)<(R))return-1;if((L)>(R))return+1
// int32_t pullcomp (const void *left, const void *right) {
// ull l = *(ull*)left;
// ull r = *(ull*)right;
// if (l < r) {
// return -1;
// }
// if (l > r) {
// return +1;
// }
// return 0;
// }
BEGCMP(pullcomp){
DEFLR(ull);
CMPRET(l, r);
return 0;
}
BEGCMP(prevcomp){
DEFLR(sll);
CMPRET(r, l);
return 0;
}
BEGCMP(psllcomp){
DEFLR(sll);
CMPRET(l, r);
return 0;
}
BEGCMP(pcharcomp){
DEFLR(char);
CMPRET(l, r);
return 0;
}
BEGCMP(pdoublecomp){
DEFLR(double);
CMPRET(l, r);
return 0;
}
int32_t pstrcomp (const void *left, const void *right) {
char* l = *(char**)left;
char* r = *(char**)right;
return strcmp(l, r);
}
BEGCMP(phwllABcomp){
DEFLR(hwll);
CMPRET(l.a, r.a);
CMPRET(l.b, r.b);
return 0;
}
BEGCMP(phwllREVcomp){
DEFLR(hwll);
CMPRET(l.b, r.b);
CMPRET(l.a, r.a);
return 0;
}
BEGCMP(ptriplecomp){
DEFLR(hwllc);
CMPRET(l.a, r.a);
CMPRET(l.b, r.b);
CMPRET(l.c, r.c);
return 0;
}
BEGCMP(ptripleREVcomp){
DEFLR(hwllc);
CMPRET(l.b, r.b);
CMPRET(l.a, r.a);
CMPRET(l.c, r.c);
return 0;
}
BEGCMP(ptripleCABcomp){
DEFLR(hwllc);
CMPRET(l.c, r.c);
CMPRET(l.a, r.a);
CMPRET(l.b, r.b);
return 0;
}
BEGCMP(phwrealcomp){
DEFLR(hwreal);
CMPRET(l.a, r.a);
CMPRET(l.b, r.b);
return 0;
}
int32_t pquadcomp (const void *left, const void *right) {
linell l = *(linell*)left;
linell r = *(linell*)right;
sll ac = phwllABcomp(&(l.a), &(r.a));
if (ac) return ac;
sll bc = phwllABcomp(&(l.b), &(r.b));
if (bc) return bc;
return 0;
}
int32_t pfracomp (const void *left, const void *right) {
hwllc l = *(hwllc*)left;
hwllc r = *(hwllc*)right;
CMPRET(l.a * r.b, l.b * r.a);
return 0;
}
bool isinrange (sll left, sll x, sll right) {
return (left <= x && x <= right);
}
bool isinrange_soft (sll left, sll x, sll right) {
return (left <= x && x <= right) || (left >= x && x >= right);
}
sll a[N_MAX + 5];
// ull a[N_MAX + 5];
// sll a[3001][3001];
sll b[N_MAX + 5];
// ull b[N_MAX + 5];
// sll b[3001][3001];
sll c[N_MAX + 5];
sll d[N_MAX + 5];
sll e[N_MAX * 4];
char s[N_MAX + 1];
// char s[3010][3010];
char t[N_MAX + 1];
// char t[3010][3010];
char u[N_MAX + 1];
hwll xy[N_MAX * 2 + 5];
hwllc tup[N_MAX + 5];
// sll table[3005][3005];
ull gin[N_MAX];
// here we go
ull depth[N_MAX];
// ull dpar[20][N_MAX];
// ull dxor[20][N_MAX];
bool isgood[N_MAX];
ull bxor[N_MAX];
bool isw[N_MAX];
void dfs (ull v, ull p) {
isw[v] = true;
for (sll i = gin[v]; i < gin[v + 1]; i++) {
ull u = tup[i].b;
if (u == p) continue;
if (isw[u]) continue;
ull e = tup[i].c;
// dpar[0][u] = v;
// dxor[0][u] = c[e];
// depth[u] = depth[v] + 1;
bxor[u] = bxor[v] ^ c[e];
isgood[e] = true;
dfs(u, v);
}
}
ull matrix[N_MAX], len = 0, rank = 0;
ull solve () {
sll i, j, ki, li;
// ull result = 0;
sll result = 0;
double dresult = 0;
// ull maybe = 0;
sll maybe = 0;
// ull sum = 0;
sll sum = 0;
sll item;
sll *dpcell;
for (i = 0; i < m; i++) {
tup[i * 2] = (hwllc){a[i], b[i], i};
tup[i * 2 + 1] = (hwllc){b[i], a[i], i};
}
qsort(tup, m * 2, sizeof(hwllc), ptriplecomp);
i = j = 0;
while (i <= n) {
gin[i] = j;
while (j < m * 2 && tup[j].a == i) j++;
i++;
}
// dpar[0][0] = 0;
// dxor[0][0] = 0;
// depth[0] = 0;
bxor[0] = 0;
dfs(0, n);
// puts("a");
// fflush(stdout);
for (i = 0; i < m; i++) {
if (isgood[i]) continue;
matrix[len++] = bxor[a[i]] ^ bxor[b[i]] ^ c[i];
}
for (i = 63; i >= 0; i--) {
for (j = rank; j < len; j++) {
if (matrix[j] & (1LL << i)) break;
}
if (j < len) {
if (!(matrix[rank] & (1LL << i))) {
matrix[rank] ^= matrix[j];
}
for (j = rank + 1; j < len; j++) {
if (matrix[j] & (1LL << i)) {
matrix[j] ^= matrix[rank];
}
}
rank++;
}
}
while (q--) {
ull x, y;
scanf("%llu%llu", &x, &y);
// x--;
// y--;
result = bxor[x] ^ bxor[y];
for (i = 0; i < rank; i++) {
result = smax(result, result ^ matrix[i]);
}
printf("%llu\n", result);
}
// printf("%lld\n", result);
// printf("%.15f\n", dresult);
// puts(s);
return 0;
success:
// puts("YES");
puts("Yes");
// printf("%llu\n", result);
// puts("0");
// puts("First");
return 0;
fail:
// puts("NO");
// puts("No");
// puts("0");
puts("-1");
// puts("-1 -1 -1");
// puts("Second");
return 1;
}
int32_t main (int argc, char *argv[]) {
int32_t i, j;
n = 5;
m = 0;
// scanf("%llu%llu", &h, &w);
scanf("%llu%llu", &n, &m);
// scanf("%llu", &k, &n, &m);
// scanf("%llu%llu", &h, &w);
scanf("%llu", &q);
// scanf("%lld", &va, &vb, &vc, &vd);
// va--;
// vb--;
// scanf("%llu%llu%llu%llu", &ua, &ub, &uc, &ud, &ue);
// scanf("%s", s);
// scanf("%s", t);
// scanf("%s", u);
// scanf("%llu", &k);
// scanf("%lld", &m);
// for (i = 0; i < n; i++) {
// scanf("%lld", &a[i]);
// // scanf("%lld", &d[i]);
// }
// scanf("%llu", &q);
for (i = 0; i < m; i++) {
// scanf("%lld%lld", &xy[i].a, &xy[i].b);
// scanf("%lld%lld%lld", &tup[i].a, &tup[i].b, &tup[i].c);
// scanf("%lld", &c[i]);
scanf("%lld", &a[i]);
scanf("%lld", &b[i]);
scanf("%lld", &c[i]);
// scanf("%lld", &d[i]);
// a[i]--;
// b[i]--;
// c[i]--;
// d[i]--;
// xy[i].a--;
// xy[i].b--;
// tup[i].a--;
// tup[i].b--;
}
// scanf("%llu", &m);
// for (i = 0; i < m; i++) {
// // scanf("%lld%lld", &a[i], &b[i]);
// scanf("%lld", &b[i]);
// // a[i]--;
// // b[i]--;
// // scanf("%lld", &c[i]);
// // scanf("%lld", &d[i]);
// // scanf("%lld", &e[i]);
// // c[i]--;
// // d[i]--;
// }
// for (i = 0; i < q; i++) {
// // scanf("%lld%lld", &xy[i].a, &xy[i].b);
// scanf("%lld", &c[i]);
// // xy[i].a--;
// // xy[i].b--;
// }
// for (i = 0; i < n; i++) {
// for (j = 0; j < m; j++) {
// scanf("%lld", &table[i][j]);
// // table[i][j]--;
// }
// }
// for (i = 0; i < h; i++) {
// scanf("%s", s[i]);
// }
// scanf("%llu", &q);
solve();
return 0;
}
Submission Info
Submission Time
2019-06-11 22:50:56+0900
Task
K - XOR回廊
User
sheyasutaka
Language
C (GCC 5.4.1)
Score
200
Code Size
8749 Byte
Status
AC
Exec Time
199 ms
Memory
30124 KB
Compile Error
./Main.c: In function ‘solve’:
./Main.c:376:9: warning: format ‘%llu’ expects argument of type ‘long long unsigned int *’, but argument 2 has type ‘ull * {aka long unsigned int *}’ [-Wformat=]
scanf("%llu%llu", &x, &y);
^
./Main.c:376:9: warning: format ‘%llu’ expects argument of type ‘long long unsigned int *’, but argument 3 has type ‘ull * {aka long unsigned int *}’ [-Wformat=]
./Main.c:385:10: warning: format ‘%llu’ expects argument of type ‘long long unsigned int’, but argument 2 has type ‘sll {aka long int}’ [-Wformat=]
printf("%llu\n", result);
^
./Main.c: In function ‘main’:
./Main.c:419:8: warning: format ‘%llu’ expects argument of type ‘long long unsigned int *’, but argument 2 has type ‘ull * {aka long unsigned int *}’ [-Wformat=]
scanf("%llu%llu", &n, &m);
^
./Main.c:419:8: warning: format ‘%llu’ expects argument of type ‘long long unsigned int *’, but argument 3 has type ‘ull * {aka long unsigned int *}’ [-Wformat=]
./Main.c:422:8: warning: format ‘%llu’ expe...
Judge Result
Set Name
Partial 1
All
Score / Max Score
60 / 60
140 / 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
4 ms
18560 KB
0_01_Teuchi_01
AC
2 ms
10368 KB
0_10_PerfectRandom_00_000004_000004
AC
4 ms
18560 KB
0_10_PerfectRandom_01_000005_000007
AC
4 ms
18560 KB
0_10_PerfectRandom_02_000009_000013
AC
4 ms
18560 KB
0_21_Star_02_000009_000008
AC
4 ms
16512 KB
0_21_Star_03_000012_000011
AC
4 ms
16512 KB
0_22_BinaryTree_01_000005_000004
AC
4 ms
16512 KB
0_23_RandomTree_00_000004_000003
AC
4 ms
16512 KB
0_25_Ring_00_000003_000003
AC
4 ms
18560 KB
0_25_Ring_01_000020_000020
AC
4 ms
18560 KB
0_26_Complete_00_000004_000006
AC
4 ms
18560 KB
0_26_Complete_01_000005_000010
AC
4 ms
18560 KB
0_27_Random_00_000002_000001
AC
4 ms
16512 KB
0_27_Random_01_000005_000010
AC
4 ms
18560 KB
0_27_Random_03_000013_000013
AC
4 ms
18560 KB
0_30_Island_00_000004_000004
AC
4 ms
18560 KB
0_30_Island_01_000007_000006
AC
4 ms
16512 KB
0_30_Island_02_000009_000008
AC
4 ms
16512 KB
0_40_Corner_00_000010_000020
AC
32 ms
20608 KB
0_40_Corner_01_000021_000020
AC
31 ms
18304 KB
1_01_Teuchi_00
AC
8 ms
17040 KB
1_10_PerfectRandom_03_000013_000021
AC
4 ms
18560 KB
1_10_PerfectRandom_04_000021_000106
AC
4 ms
18556 KB
1_10_PerfectRandom_05_000029_000210
AC
4 ms
18556 KB
1_10_PerfectRandom_06_000236_007490
AC
10 ms
18588 KB
1_10_PerfectRandom_07_000843_061761
AC
53 ms
20780 KB
1_10_PerfectRandom_08_004086_126064
AC
108 ms
25060 KB
1_10_PerfectRandom_09_007303_126754
AC
110 ms
25284 KB
1_10_PerfectRandom_10_064317_081046
AC
87 ms
24740 KB
1_10_PerfectRandom_11_069565_075242
AC
83 ms
24500 KB
1_20_Line_08_003103_003102
AC
7 ms
16744 KB
1_20_Line_09_002580_002579
AC
6 ms
16892 KB
1_20_Line_10_069209_069208
AC
84 ms
25676 KB
1_22_BinaryTree_06_000398_000397
AC
4 ms
16636 KB
1_23_RandomTree_05_000060_000059
AC
4 ms
16508 KB
1_24_SkewTree_04_000069_000068
AC
4 ms
16508 KB
1_24_SkewTree_07_000796_000795
AC
4 ms
16636 KB
1_24_SkewTree_11_098814_098813
AC
117 ms
23396 KB
1_25_Ring_02_001000_001000
AC
5 ms
18684 KB
1_25_Ring_03_100000_100000
AC
122 ms
30124 KB
1_26_Complete_02_000067_002211
AC
6 ms
18684 KB
1_26_Complete_03_000500_124750
AC
133 ms
24868 KB
1_27_Random_02_000008_000022
AC
4 ms
18556 KB
1_27_Random_04_000039_000581
AC
5 ms
18684 KB
1_27_Random_05_000050_000407
AC
5 ms
18556 KB
1_27_Random_06_000307_020347
AC
21 ms
18624 KB
1_27_Random_07_000551_065255
AC
58 ms
20744 KB
1_27_Random_08_006629_062527
AC
58 ms
21128 KB
1_27_Random_09_009865_050301
AC
51 ms
21316 KB
1_27_Random_10_042323_075720
AC
82 ms
24988 KB
1_27_Random_11_043628_107061
AC
120 ms
25440 KB
1_30_Island_03_000013_000063
AC
4 ms
18556 KB
1_30_Island_04_000094_000093
AC
4 ms
16508 KB
1_30_Island_05_000039_000038
AC
4 ms
16508 KB
1_30_Island_06_000364_000363
AC
4 ms
16636 KB
1_30_Island_07_000951_000952
AC
5 ms
18684 KB
1_30_Island_08_005937_005936
AC
10 ms
16740 KB
1_30_Island_09_008024_008090
AC
13 ms
18816 KB
1_30_Island_10_011040_047244
AC
52 ms
21076 KB
1_30_Island_11_046719_053967
AC
64 ms
21912 KB
1_30_Island_12_099995_164170
AC
199 ms
29676 KB
1_30_Island_13_099996_159191
AC
196 ms
29652 KB
1_30_Island_14_099992_157444
AC
192 ms
29732 KB