QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#277433	#6679. Not Another Path Query Problem	ucup-team191^#	WA	13ms	16104kb	C++14	1.5kb	2023-12-06 18:54:22	2023-12-06 18:54:24

Judging History

This is the latest submission verdict.

[2023-12-06 18:54:24]
Judged

Verdict: WA
Time: 13ms
Memory: 16104kb

Show

[2023-12-06 18:54:22]
Submitted

answer

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 500005;

int n, m, q;
llint V;
int a[MAXN], b[MAXN], qa[MAXN], qb[MAXN];
llint w[MAXN];
int par[MAXN], sol[MAXN];

int nadi (int x) {
    if (x == par[x]) return x;
    return par[x] = nadi(par[x]);
}

void spoji (int x, int y) {
    par[nadi(x)] = nadi(y);
}

void calc (llint mask) {
    for (int i = 1; i <= n; i++) {
        par[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        if ((w[i] & mask) == mask) {
            spoji(a[i], b[i]);
        }
    }
    for (int i = 1; i <= q; i++) {
        if (nadi(qa[i]) == nadi(qb[i])) {
            sol[i] = 1;
        }
    }
}

int main () {
    cin >> n >> m >> q >> V;
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> w[i];
    }
    for (int i = 1; i <= q; i++) {
        cin >> qa[i] >> qb[i];
    }

    if (V == 0) {
        calc(0);
        for (int i = 1; i <= q; i++) {
            if (sol[i]) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }

    V--;
    for (int i = 0; i < 60; i++) {
        if ((V & (1LL << i)) == 0) {
            llint bit = (1LL << i);
            llint mask = (V | (bit - 1)) ^ (bit - 1) + bit;
            calc(mask);
        }
    }
    for (int i = 1; i <= q; i++) {
        if (sol[i]) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 15944kb

input:

output:

Yes
No
Yes
No

result:

ok 4 token(s): yes count is 2, no count is 2

Test #2:

score: 0

Accepted

time: 3ms

memory: 15856kb

input:

output:

Yes

result:

ok YES

Test #3:

score: -100

Wrong Answer

time: 13ms

memory: 16104kb

input:

100 2000 50000 0
32 52 69658009083393280
26 38 868250171554967916
87 32 743903879320440454
22 15 19782587273744714
57 98 845866434191429143
42 95 1145336983294966993
67 40 1036117659380117375
46 24 265457274847122243
63 44 438254608190938148
28 23 992625102587165494
57 87 558124114385470345
6 17 535...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

wrong answer Output contains longer sequence [length = 100000], but answer contains 50000 elements