QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#675616#6613. Bitwise Exclusive-OR Sequenceivyoruska#TL 81ms66252kbC++202.0kb2024-10-25 18:58:412024-10-25 18:58:41

Judging History

你现在查看的是最新测评结果

  • [2024-10-25 18:58:41]
  • 评测
  • 测评结果:TL
  • 用时:81ms
  • 内存:66252kb
  • [2024-10-25 18:58:41]
  • 提交

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...

output:


result: