QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#666829#7158. Carnival GeneralKhiem#29 0ms4116kbC++141.3kb2024-10-22 20:07:522024-10-22 20:07:54

Judging History

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

  • [2024-10-22 20:07:54]
  • 评测
  • 测评结果:29
  • 用时:0ms
  • 内存:4116kb
  • [2024-10-22 20:07:52]
  • 提交

answer

#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 1005;
vector<int> g[N];
int a[N], dp[256][8], V[N];
pair<int,int> up[256][8];
signed main(){
    int n; scanf("%d", &n);
    for(int i = 1; i<n; ++i){
        for(int j = 0; j<i; ++j) scanf("%d", a+j);
        int sz = i/2 + (i&1);
        for(int j = 0; j<sz; ++j){
            int u = i, v = a[j];
            g[u].push_back(v); g[v].push_back(u);
        }
    }
    for(int i = 0; i<n; ++i) dp[1<<i][i] = 1;
    int lim = 1<<n;
    for(int msk = 0; msk<lim; ++msk){
        for(int i = 0; i<n; ++i){
            if(msk>>i&1){
                int pmsk = msk ^ (1<<i);
                for(int j: g[i]){
                    if(pmsk>>j&1 && dp[pmsk][j]){
                        dp[msk][i] = 1;
                        up[msk][i] = {pmsk, j};
                        break;
                    }    
                }
                
            }
        }
    }
    int msk = lim-1, j, m = 0;
    for(int i = 0; i<n; ++i) if(dp[msk][i]){ j = i; break;}
    for(; ; ){
        V[m++] = j;
        if(__builtin_popcount(msk) == 1) break;
        pair<int,int> tmp = up[msk][j];
        msk = tmp.first; j = tmp.second;
    }
    for(int i = m-1; ~i; --i) printf("%d ", V[i]);
}

詳細信息

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 11
Accepted
time: 0ms
memory: 3792kb

input:

2
0

output:

1 0 

result:

ok correct

Test #2:

score: 0
Runtime Error

input:

99
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0
5 4 3 2 1 0
6 5 4 3 2 1 0
7 6 5 4 3 2 1 0
8 7 6 5 4 3 2 1 0
9 8 7 6 5 4 3 2 1 0
10 9 8 7 6 5 4 3 2 1 0
11 10 9 8 7 6 5 4 3 2 1 0
12 11 10 9 8 7 6 5 4 3 2 1 0
13 12 11 10 9 8 7 6 5 4 3 2 1 0
14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
16 1...

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #6:

score: 23
Accepted
time: 0ms
memory: 3860kb

input:

2
0

output:

1 0 

result:

ok correct

Test #7:

score: 0
Runtime Error

input:

99
0
0 1
0 1 2
0 1 2 3
0 1 2 3 4
0 1 2 3 4 5
0 1 2 3 4 5 6
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10 11
0 1 2 3 4 5 6 7 8 9 10 11 12
0 1 2 3 4 5 6 7 8 9 10 11 12 13
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 ...

output:


result:


Subtask #3:

score: 29
Accepted

Test #12:

score: 29
Accepted
time: 0ms
memory: 3816kb

input:

2
0

output:

1 0 

result:

ok correct

Test #13:

score: 29
Accepted
time: 0ms
memory: 3804kb

input:

8
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0
5 4 3 2 1 0
6 5 4 3 2 1 0

output:

7 6 5 4 3 2 1 0 

result:

ok correct

Test #14:

score: 29
Accepted
time: 0ms
memory: 3804kb

input:

8
0
0 1
0 1 2
0 1 2 3
0 1 2 3 4
0 1 2 3 4 5
0 1 2 3 4 5 6

output:

6 2 5 1 4 0 7 3 

result:

ok correct

Test #15:

score: 29
Accepted
time: 0ms
memory: 3828kb

input:

8
0
0 1
0 1 2
2 1 0 3
4 3 0 2 1
4 3 0 5 2 1
6 5 2 1 4 0 3

output:

6 7 2 4 5 3 1 0 

result:

ok correct

Test #16:

score: 29
Accepted
time: 0ms
memory: 4116kb

input:

8
0
1 0
0 1 2
3 2 1 0
0 1 2 3 4
5 4 3 2 1 0
0 1 2 3 4 5 6

output:

7 3 4 6 5 2 1 0 

result:

ok correct

Test #17:

score: 29
Accepted
time: 0ms
memory: 3792kb

input:

3
0
0 1

output:

2 0 1 

result:

ok correct

Test #18:

score: 29
Accepted
time: 0ms
memory: 4100kb

input:

5
0
1 0
0 2 1
1 3 2 0

output:

4 3 2 1 0 

result:

ok correct

Test #19:

score: 29
Accepted
time: 0ms
memory: 3792kb

input:

6
0
0 1
0 1 2
0 2 1 3
0 2 3 4 1

output:

4 2 5 3 1 0 

result:

ok correct

Test #20:

score: 29
Accepted
time: 0ms
memory: 3820kb

input:

7
0
1 0
2 0 1
2 0 1 3
0 1 4 2 3
3 2 4 0 5 1

output:

5 4 6 3 2 1 0 

result:

ok correct

Test #21:

score: 29
Accepted
time: 0ms
memory: 3832kb

input:

8
0
1 0
0 1 2
3 2 0 1
3 1 0 4 2
4 2 0 3 5 1
6 4 3 1 5 2 0

output:

5 3 7 6 4 2 1 0 

result:

ok correct

Test #22:

score: 29
Accepted
time: 0ms
memory: 3764kb

input:

8
0
0 1
2 1 0
3 0 2 1
4 0 3 1 2
4 0 2 5 3 1
4 5 1 2 0 6 3

output:

7 5 4 6 2 3 1 0 

result:

ok correct

Test #23:

score: 29
Accepted
time: 0ms
memory: 4076kb

input:

8
0
0 1
0 1 2
3 2 1 0
4 3 2 1 0
5 4 3 2 1 0
6 5 4 3 2 1 0

output:

7 6 5 2 4 3 1 0 

result:

ok correct

Test #24:

score: 29
Accepted
time: 0ms
memory: 3868kb

input:

8
0
1 0
2 1 0
0 1 2 3
0 1 2 3 4
0 1 2 3 4 5
0 1 2 3 4 5 6

output:

6 2 5 1 4 0 7 3 

result:

ok correct

Test #25:

score: 29
Accepted
time: 0ms
memory: 3888kb

input:

8
0
1 0
1 0 2
1 3 0 2
1 3 0 2 4
1 3 5 0 2 4
1 3 5 0 2 4 6

output:

2 1 4 3 6 5 7 0 

result:

ok correct

Test #26:

score: 29
Accepted
time: 0ms
memory: 4068kb

input:

6
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0

output:

5 4 3 2 1 0 

result:

ok correct

Test #27:

score: 29
Accepted
time: 0ms
memory: 3792kb

input:

5
0
0 1
0 1 2
0 1 2 3

output:

4 1 3 0 2 

result:

ok correct

Test #28:

score: 29
Accepted
time: 0ms
memory: 3796kb

input:

4
0
1 0
0 2 1

output:

3 2 1 0 

result:

ok correct

Subtask #4:

score: 0
Skipped

Dependency #1:

0%