Submission #64405442

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
struct edge_s {
  int to;
  int value;
};
int ec[212345];
struct edge_s* es[212345];
void ae(int f, int t, int v) {
  es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
  if (es[f] == NULL) exit(2);
  es[f][ec[f]++] = (struct edge_s){ t, v };
}
int value[212345];
int count[32][2];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>

struct edge_s {
	int to;
	int value;
};

int ec[212345];
struct edge_s* es[212345];

void ae(int f, int t, int v) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = (struct edge_s){ t, v };
}

int value[212345];
int count[32][2];

int cnt;
int targets[212345];

int ans[212345];

void dfs(int node, int cur_value) {
	if (value[node] >= 0) {
		if (value[node] != cur_value) {
			puts("-1");
			exit(0);
		}
	} else {
		int i;
		for (i = 0; i < 31; i++) {
			count[i][(cur_value >> i) & 1]++;
		}
		value[node] = cur_value;
		targets[cnt++] = node;
		for (i = 0; i < ec[node]; i++) {
			dfs(es[node][i].to, cur_value ^ es[node][i].value);
		}
	}
}

int main(void) {
	int N, M;
	int i;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		int X, Y, Z;
		if (scanf("%d%d%d", &X, &Y, &Z) != 3) return 1;
		ae(X, Y, Z);
		ae(Y, X, Z);
	}
	memset(value, -1, sizeof(value));
	for (i = 1; i <= N; i++) {
		if (value[i] < 0) {
			int j;
			int meow = 0;
			memset(count, 0, sizeof(count));
			cnt = 0;
			dfs(i, 0);
			for (j = 0; j < 31; j++) {
				if (count[j][0] < count[j][1]) meow |= 1 << j;
			}
			for (j = 0; j < cnt; j++) {
				ans[targets[j]] = value[targets[j]] ^ meow;
			}
		}
	}
	for (i = 0; i < N; i++) {
		printf(" %d" + !i, ans[i + 1]);
	}
	putchar('\n');
	return 0;
}

/*

各連結成分ごとに、1箇所決めるとほかも全部決まる
各ビットについて 0 or 1 の数をそれぞれ数え、多くない方を採用
矛盾したら失格

*/

Submission Info

Judge Result