QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#684431#7303. City UnitedAfterlifeWA 76ms9936kbC++201.7kb2024-10-28 13:24:072024-10-28 13:24:08

Judging History

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

  • [2024-10-28 13:24:08]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:9936kb
  • [2024-10-28 13:24:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n , m;
vector<int> E[55];
const int N = 1.6e6;
short f[2][N] ;
int pw[15];
void upd(short &x,short y) {
    ((x += y) &= 3) ;
}
int work(int x) {
    if(x >= pw[13]) x -= pw[13];
    if(x >= pw[13]) x -= pw[13];
    return x;
}
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    cin >> n >> m;
    pw[0] = 1;
    for(int i = 1;i <= 14;i++) pw[i] = 3 * pw[i - 1];
    for(int i = 1;i <= m;i++) {
        int u , v;
        cin >> u >> v;
        if(u > v) swap(u , v);
        E[v].push_back(u) ;
    }
    f[0][0] = 1;
    int cur = 0;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < pw[min(i + 1 , 13)] ; j++) f[cur ^ 1][j] = 0;
        for(int j = 0;j < pw[min(i , 13)] ;j++) {
            int g[13] = {0} , t = j;
            for(int k = 0;k < 12;k++) {
                g[k] = t % 3 ; t /= 3;
            }
            for(int d = 0;d < 3;d++) {
                if(d == 2) upd(f[cur ^ 1][work(j * 3 + 2)] , f[cur][j]) ;
                else {
                    bool ff = 1;
                    for(auto v : E[i + 1]) {
                        if(g[i - v] == 1 - d) {ff = 0 ; break ;}
                    }
                    if(ff) upd(f[cur ^ 1][work(j * 3 + d)] , f[cur][j]) ;
                }
            }
            // printf("%d : ",i) ;
            // for(int k = 0;k < min(i , 13);k++) printf("%d ",g[k]) ;
            // printf(" : %d\n",f[cur][j]) ;
        }
        cur ^= 1;
    }
    short ans = 3;
    for(int j = 0;j < pw[min(n , 13)] ; j++) {
        // ans += f[cur][j];
        upd(ans , f[cur][j]) ;
    }
    // cout << ans << '\n';
    if(ans == 2) cout << 1 << '\n';
    else cout << 0 << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5668kb

input:

3 2
1 2
2 3

output:

0

result:

ok 1 number(s): "0"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5708kb

input:

3 3
1 2
2 3
3 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 74ms
memory: 9876kb

input:

15 31
9 5
14 5
2 7
5 15
11 14
11 9
2 6
3 4
12 1
6 8
3 5
11 10
15 6
4 1
1 2
8 9
6 12
14 10
13 2
4 5
3 8
3 15
11 6
7 5
4 6
11 2
13 15
3 2
8 4
6 13
7 10

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 76ms
memory: 9788kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 70ms
memory: 9816kb

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 66ms
memory: 9868kb

input:

15 45
13 15
3 15
5 4
15 14
6 10
2 3
10 11
9 8
8 7
10 4
9 2
3 8
15 2
2 6
15 9
6 15
10 7
8 2
5 6
14 10
12 10
8 1
11 3
3 12
2 1
11 15
11 5
2 7
1 11
8 4
1 6
14 5
5 2
13 1
7 11
4 12
12 14
15 5
7 5
10 2
4 7
13 2
4 14
12 1
12 11

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 71ms
memory: 9868kb

input:

15 48
5 14
11 1
6 8
10 3
10 6
3 4
3 8
15 3
10 15
2 11
5 15
7 10
7 14
5 10
2 9
9 3
11 4
11 7
12 5
9 10
10 14
10 2
13 11
2 8
10 13
2 3
7 12
13 3
10 8
12 10
15 12
4 7
9 13
7 13
5 7
2 13
11 14
9 15
6 15
8 12
2 6
1 13
3 14
4 15
5 3
6 3
4 10
2 7

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 73ms
memory: 9792kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #9:

score: 0
Accepted
time: 66ms
memory: 9780kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 70ms
memory: 9848kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: -100
Wrong Answer
time: 76ms
memory: 9936kb

input:

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

output:

0

result:

wrong answer 1st numbers differ - expected: '1', found: '0'