QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#675616 | #6613. Bitwise Exclusive-OR Sequence | ivyoruska# | TL | 81ms | 66252kb | C++20 | 2.0kb | 2024-10-25 18:58:41 | 2024-10-25 18:58:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 res;
struct Bipartite_graph {
int n;
vector<vector<pair<int,int> > > gra;
vector<int> col;
int w;
void init(int x) {
n = x;
gra.resize(n + 1);
col.resize(n + 1);
}
void add_edge(int u, int v,int op) {
gra[u].emplace_back(v,op);
gra[v].emplace_back(u,op);
}
int num1;
int num2;
bool dfs(int x) {
if(col[x]==0)num1++;
else num2++;
for (auto& [y,op] : gra[x]) {
if (col[y] == -1) {
if(op)col[y] = col[x] ^ 1;
else col[y]=col[x];
if (!dfs(y))return false;
}
else if (col[y] == col[x]&&op)
return false;
else if(col[x]==1^col[y]&&!op)
return false;
}
return true;
}
bool work() {
for (int i = 1; i <= n; i++)col[i] = -1;
for (int i = 1; i <= n; i++) {
if (col[i] == -1) {
num1 = 0;
num2 = 0;
col[i] = 0;
if (dfs(i)) {
res += 1LL * min(num1,num2) * (1 << w);
}
else return false;
}
}
return true;
}
}gra[40];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m; cin >> n >> m;
for (int i = 0; i <= 30; i++) {
gra[i].init(n);
gra[i].w = i;
}
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
for (int j = 30; j >= 0; j--) {
if (w & (1 << j)) {
gra[j].add_edge(u, v,1);
}
else gra[j].add_edge(u,v,0);
}
}
for (int i = 30; i >= 0; i--) {
if (!gra[i].work()) {
cout << -1 << '\n';
return 0;
}
}
cout << res;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
3 2 1 2 1 2 3 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
3 3 1 2 1 2 3 1 1 3 1
output:
-1
result:
ok 1 number(s): "-1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
5 5 3 4 12 3 1 20 2 5 16 1 4 24 4 5 19
output:
58
result:
ok 1 number(s): "58"
Test #4:
score: 0
Accepted
time: 81ms
memory: 66144kb
input:
500 124750 1 2 31473 1 3 11597 1 4 6686 1 5 1214 1 6 14442 1 7 1042 1 8 19057 1 9 22648 1 10 24461 1 11 25714 1 12 3976 1 13 31954 1 14 7384 1 15 13988 1 16 28651 1 17 31599 1 18 8786 1 19 27068 1 20 9645 1 21 28281 1 22 11681 1 23 28897 1 24 31916 1 25 10462 1 26 23973 1 27 4615 1 28 5124 1 29 2026...
output:
8041745
result:
ok 1 number(s): "8041745"
Test #5:
score: 0
Accepted
time: 69ms
memory: 66252kb
input:
500 124750 1 2 3902 1 3 9006 1 4 2914 1 5 8753 1 6 2395 1 7 21406 1 8 14552 1 9 25834 1 10 28282 1 11 9684 1 12 11347 1 13 20545 1 14 16324 1 15 16951 1 16 11594 1 17 5035 1 18 17726 1 19 831 1 20 23194 1 21 7693 1 22 6147 1 23 315 1 24 32755 1 25 17078 1 26 11348 1 27 9587 1 28 21015 1 29 881 1 30 ...
output:
7803950
result:
ok 1 number(s): "7803950"
Test #6:
score: -100
Time Limit Exceeded
input:
100000 200000 82262 26109 1005476194 43106 86715 475153289 59086 60577 507254441 71498 80384 186530379 99676 3003 289537598 30772 72897 345346447 12686 87447 896623879 12520 27709 26442442 82734 20830 967590473 13380 76164 927495776 25723 55377 89078582 7173 86993 669894679 37790 94846 331905713 365...