QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#613679	#7798. Colorful Village	xyyy	WA	2ms	12028kb	C++17	1.7kb	2024-10-05 14:27:34	2024-10-05 14:28:01

Judging History

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

[2024-10-05 14:28:01]
评测

测评结果：WA
用时：2ms
内存：12028kb

查看

[2024-10-05 14:27:34]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define rep(i, f, l) for(int i(f); i <= l; ++i)
#define per(i, f, l) for(int i(f); i >= l; --i)
const int N = 2e5 + 5;
const int M = 1e3 + 5;
int n;
int c[N];
int Next[N << 1], head[N], ver[N << 1], tot;

void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}
int dfn[N], low[N], cnt, vis[N], stk[N], top, co[N], sum;
bool fl = 0;
int total;
bool ex[N];
int lin[N];

void dfs(int x, int cnt) {
    if (cnt == n) {
        fl = 1;
        for (int i = 1; i <= n; i++)
            cout << lin[i] << " ";
        cout << endl;
        return;
    }
    if (fl == 1)
        return;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (ex[c[y]] == 0) {
            ex[c[y]] = 1;
            lin[cnt + 1] = y;
            dfs(y, cnt + 1);
            ex[c[y]] = 0;
        }
        if (fl == 1)
            return;
    }
}

void work() {
    cin >> n;
    for (int i = 1; i <= 2 * n; i++) {
        cin >> c[i];
    }
    memset(head, 0, sizeof(head));
    tot = 0;
    for (int i = 1; i < 2 * n; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    fl = 0;
    for (int i = 1; i <= 2 * n; i++) {
        if (c[i] == 1) {
                memset(ex,0,sizeof(ex));
            ex[1] = 1;
            lin[1] = i;
            dfs(i, 1);
            if(fl==1)break;
        }
    }
    if (fl == 0)
        cout << "-1" << endl;
    return;
}

signed main() {
//  ios::sync_with_stdio(0);
//  cin.tie(0);
//  cout.tie(0);
    int t ;
    cin >> t;
    while (t--) {
        work();
    }
    return 0;
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 11836kb

input:

2
4
1 3 1 3 4 4 2 2
1 6
5 3
2 4
7 1
7 5
5 8
2 5
3
1 1 2 2 3 3
1 2
2 3
3 4
4 5
5 6

output:

1 7 5 2 
-1

result:

ok ok, 1 yes, 1 no (2 test cases)

Test #2:

score: 0

Accepted

time: 0ms

memory: 11804kb

input:

output:

result:

ok ok, 1 yes, 0 no (1 test case)

Test #3:

score: 0

Accepted

time: 2ms

memory: 12028kb

input:

5
1
1 1
2 1
1
1 1
2 1
3
3 2 3 1 1 2
4 1
6 1
3 5
5 1
2 4
4
3 3 1 1 4 4 2 2
2 7
7 6
1 2
8 1
4 2
2 5
3 1
1
1 1
1 2

output:

result:

ok ok, 5 yes, 0 no (5 test cases)

Test #4:

score: -100

Wrong Answer

time: 0ms

memory: 11884kb

input:

10
3
3 2 3 1 1 2
3 1
3 4
2 5
5 3
6 4
15
8 9 13 12 2 4 11 15 10 10 1 12 8 6 15 7 9 5 3 6 14 14 13 3 1 7 11 5 4 2
24 30
1 26
2 16
4 7
30 19
3 19
13 11
21 25
23 22
30 4
19 27
17 26
16 17
21 7
23 25
15 11
10 8
4 16
2 11
14 16
5 10
22 6
11 5
21 18
15 29
24 9
28 19
23 12
13 20
23
21 20 5 9 18 20 21 9 3 6 ...

output:

-1
-1
-1
-1
-1
-1
7 1 5 8 2 
-1
-1
-1

result:

wrong answer jury found a solution but participant did not (test case 1)