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
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
AC × 21
AC × 64
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