QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#471460 | #7303. City United | Aria_Math | TL | 660ms | 88612kb | C++17 | 1.1kb | 2024-07-10 21:20:05 | 2024-07-10 21:20:05 |
Judging History
answer
// They say that life is always easier
// After you let yourself come undone
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 55;
const int K = 13;
const int M = 1594323;
int n, m, G[N][K], pre[14];
short f[N][M];
int main() {
//freopen("data.in", "r", stdin);
//freopen("code.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
if(u > v) swap(u, v);
G[v][v - u] = 1;
}
f[0][0] = 1;
for(int u = 1; u <= n; ++u)
for(int S = 0; S < M; ++S) if(f[u - 1][S]) {
int tmp = S;
for(int i = 1; i <= 13; ++i)
pre[i] = tmp % 3, tmp /= 3;
for(int x : {0, 1, 2}) {
pre[0] = x;
bool isOK = 1;
if(x) for(int i = 1; i <= 13; ++i)
if(G[u][i] && pre[i] && x != pre[i]) isOK = 0;
if(!isOK) continue;
int T = 0, now = 1;
for(int i = 0; i < 13; ++i)
T += pre[i] * now, now *= 3;
f[u][T] = (f[u][T] + f[u - 1][S]) & 3;
}
}
short ans = 0;
for(int S = 0; S < M; ++S)
ans = (ans + f[n][S]) & 3;
printf("%d\n", ans / 2);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 3920kb
input:
3 2 1 2 2 3
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 3ms
memory: 3848kb
input:
3 3 1 2 2 3 3 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 8ms
memory: 7792kb
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: 17ms
memory: 7148kb
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: 14ms
memory: 7348kb
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: 16ms
memory: 8220kb
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: 10ms
memory: 8676kb
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: 19ms
memory: 7112kb
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: 14ms
memory: 7068kb
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: 15ms
memory: 7108kb
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: 0
Accepted
time: 12ms
memory: 7196kb
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:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 19ms
memory: 7076kb
input:
15 103 13 9 2 6 13 1 7 6 1 3 3 7 1 14 9 3 4 5 14 8 14 13 10 9 13 4 12 10 14 15 1 4 11 10 8 7 7 11 6 9 14 6 10 5 1 8 11 8 7 2 5 6 5 3 2 10 1 11 3 4 7 13 14 3 4 10 12 5 9 12 5 1 1 6 12 2 2 11 9 1 1 7 8 9 10 15 3 2 7 10 2 9 12 7 2 4 1 12 2 5 2 14 3 10 4 14 10 6 14 10 11 4 14 11 15 11 2 8 11 6 15 6 15 7...
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 540ms
memory: 77984kb
input:
50 30 12 11 47 46 29 28 40 41 29 30 27 28 15 14 1 2 46 45 8 9 16 15 34 33 50 49 45 44 13 14 42 41 35 34 20 19 18 17 48 49 48 47 2 3 23 24 11 10 31 30 40 39 36 35 7 6 23 22 4 3
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 278ms
memory: 60044kb
input:
50 42 24 23 31 30 44 43 9 8 4 5 33 32 41 42 28 27 3 4 18 17 15 14 28 29 2 1 42 43 39 38 6 5 20 21 49 48 25 26 22 23 50 49 9 10 34 35 44 45 31 32 18 19 38 37 36 37 8 7 13 12 27 26 47 46 34 33 24 25 10 11 13 14 12 11 22 21 46 45 20 19 3 2 17 16
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 501ms
memory: 75036kb
input:
50 29 21 20 23 24 21 22 5 4 25 24 28 29 27 26 8 7 1 2 27 28 39 40 32 33 45 44 43 42 47 48 48 49 30 31 38 37 14 15 32 31 38 39 35 34 7 6 46 45 15 16 9 10 36 35 13 12 16 17
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 193ms
memory: 54316kb
input:
50 48 43 44 24 25 35 36 15 14 1 2 46 47 23 22 10 9 46 45 34 33 3 4 12 11 43 42 22 21 40 41 17 16 20 19 32 31 33 32 23 24 6 5 7 8 44 45 16 15 36 37 14 13 39 38 41 42 35 34 48 49 37 38 5 4 29 30 2 3 19 18 13 12 48 47 29 28 9 8 25 26 11 10 27 26 31 30 49 50 39 40 21 20 7 6 28 27
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 211ms
memory: 54224kb
input:
50 48 17 16 22 21 27 28 43 44 30 29 6 7 13 12 50 49 28 29 11 12 21 20 2 3 31 32 43 42 7 8 11 10 19 20 3 4 41 42 8 9 26 27 38 37 5 4 24 25 33 32 23 24 9 10 49 48 19 18 40 41 36 37 45 46 44 45 47 48 39 40 13 14 46 47 34 33 26 25 17 18 14 15 36 35 1 2 15 16 38 39 23 22 5 6 35 34
output:
1
result:
ok 1 number(s): "1"
Test #18:
score: 0
Accepted
time: 252ms
memory: 61828kb
input:
50 48 30 29 32 30 12 10 20 21 40 39 28 26 4 3 34 36 20 18 4 2 31 30 34 35 46 45 43 44 7 9 43 41 42 40 8 9 49 48 38 36 10 11 28 27 46 47 21 19 6 8 14 13 32 31 6 4 6 7 45 43 37 38 14 16 35 36 12 14 15 17 20 22 25 26 31 33 22 24 5 7 45 47 11 13 23 21 42 43 32 34 29 27 40 41 24 25
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 78ms
memory: 40076kb
input:
50 93 46 44 27 26 1 2 13 11 44 45 18 16 37 35 47 49 19 20 34 33 16 15 23 21 7 6 34 35 28 29 48 46 14 16 6 8 22 20 6 4 30 32 13 14 14 12 4 5 50 49 26 28 31 29 50 48 18 19 19 21 47 46 36 34 11 9 13 12 2 4 8 7 8 9 10 9 17 15 14 15 20 21 3 5 11 12 30 31 43 42 3 4 40 38 1 3 35 36 44 42 48 47 47 45 37 38 ...
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 121ms
memory: 47364kb
input:
50 72 20 19 11 12 2 3 11 10 18 19 49 47 25 27 40 41 4 6 26 25 23 21 18 16 33 34 13 15 35 34 17 16 45 44 38 37 44 46 14 13 14 12 28 26 24 26 32 31 49 48 42 41 6 8 43 45 8 10 29 28 24 25 4 5 20 22 39 41 3 1 19 21 23 25 24 22 47 46 33 31 8 7 38 36 37 39 16 15 36 37 12 13 42 43 32 30 35 33 32 34 41 43 4...
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 110ms
memory: 42428kb
input:
50 84 16 15 12 14 35 37 24 22 44 42 17 19 30 32 36 38 24 23 36 37 34 36 21 23 33 34 19 20 45 46 22 20 10 12 42 41 25 27 26 27 34 32 15 13 26 25 21 22 7 6 28 30 40 38 1 3 47 49 39 37 29 31 13 14 28 29 35 34 8 6 44 46 30 29 44 45 48 46 33 35 49 50 36 35 11 12 21 19 42 43 7 5 2 1 47 46 33 32 13 12 16 1...
output:
1
result:
ok 1 number(s): "1"
Test #22:
score: 0
Accepted
time: 93ms
memory: 40452kb
input:
50 92 16 14 20 18 5 4 43 41 36 37 42 40 17 15 13 11 45 47 19 21 23 25 3 2 23 21 14 15 33 34 50 49 21 22 37 39 27 29 40 39 4 3 31 32 1 2 25 24 8 9 50 48 32 30 39 41 33 35 48 49 27 25 26 25 3 1 34 36 45 43 12 10 26 28 22 24 45 46 29 30 10 9 7 5 31 33 46 48 18 16 9 11 42 43 30 28 33 32 45 44 22 23 19 1...
output:
1
result:
ok 1 number(s): "1"
Test #23:
score: 0
Accepted
time: 67ms
memory: 36400kb
input:
50 128 32 29 19 18 41 43 41 38 21 19 24 22 47 46 37 38 30 27 39 36 17 18 30 33 13 12 44 47 42 45 13 14 26 25 18 20 45 43 3 6 6 4 28 27 15 16 37 35 42 43 42 39 18 16 37 36 37 40 12 14 13 16 35 34 32 31 8 5 38 39 17 19 32 34 2 5 35 32 9 8 26 27 34 36 16 17 12 11 34 31 2 3 25 22 39 40 7 8 34 37 2 4 50 ...
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 660ms
memory: 88612kb
input:
50 30 5 6 20 22 28 31 5 7 13 11 32 35 21 18 24 22 17 15 7 8 9 6 36 33 44 43 38 39 2 4 3 2 25 24 40 41 45 44 45 47 50 47 32 29 31 29 23 26 45 46 49 47 19 21 44 41 24 21 47 46
output:
1
result:
ok 1 number(s): "1"
Test #25:
score: 0
Accepted
time: 90ms
memory: 39480kb
input:
50 114 37 34 2 5 45 47 4 3 42 40 27 24 4 6 27 28 25 24 21 20 31 33 17 16 40 43 30 31 19 16 45 46 4 2 42 41 17 15 13 14 29 28 37 36 35 34 25 22 7 10 6 5 11 8 42 45 22 23 37 40 9 7 38 41 8 7 32 29 3 6 22 19 48 46 25 27 43 46 23 26 38 36 5 7 37 35 33 34 26 24 31 34 18 20 20 19 14 15 42 44 16 18 47 46 1...
output:
0
result:
ok 1 number(s): "0"
Test #26:
score: 0
Accepted
time: 89ms
memory: 38340kb
input:
50 103 5 6 24 25 49 48 8 5 46 44 12 14 5 3 20 19 2 3 17 14 24 22 10 12 25 22 19 18 6 9 26 28 20 17 13 12 40 39 40 38 32 31 36 39 1 3 4 6 42 39 26 25 5 7 35 37 39 41 4 7 31 30 27 30 16 15 11 8 47 45 3 4 35 32 41 40 23 25 24 26 13 10 44 47 42 41 34 35 7 9 8 7 31 34 17 15 35 38 14 16 18 16 16 13 13 15 ...
output:
1
result:
ok 1 number(s): "1"
Test #27:
score: 0
Accepted
time: 57ms
memory: 34228kb
input:
50 133 18 15 13 16 44 42 35 32 36 34 48 49 17 18 1 4 7 8 3 6 49 47 33 35 22 24 34 35 46 43 27 26 14 12 4 6 42 43 11 14 31 28 40 42 20 18 27 30 30 31 3 5 35 36 18 21 21 24 32 31 40 37 38 35 19 18 22 23 20 22 24 26 40 39 3 4 20 17 4 5 42 45 11 9 4 2 9 10 32 30 11 8 9 12 43 41 38 37 20 23 5 6 46 44 13 ...
output:
0
result:
ok 1 number(s): "0"
Test #28:
score: 0
Accepted
time: 53ms
memory: 33760kb
input:
50 140 43 40 31 30 45 43 27 29 39 36 28 29 26 23 10 8 24 21 3 7 39 35 47 45 33 35 46 49 46 48 20 24 28 24 27 23 9 8 31 28 36 35 6 2 23 20 30 33 38 42 13 16 44 41 29 32 3 1 8 12 5 7 12 10 7 10 45 49 14 13 30 32 14 10 47 50 24 25 5 2 45 46 36 40 27 28 9 11 15 11 31 35 44 42 34 36 5 3 6 5 42 45 31 34 9...
output:
1
result:
ok 1 number(s): "1"
Test #29:
score: 0
Accepted
time: 73ms
memory: 38240kb
input:
50 128 3 4 15 14 22 18 33 29 23 24 13 11 45 48 17 20 24 27 21 24 46 44 26 28 8 9 42 39 26 23 43 40 5 7 36 38 36 39 21 17 37 33 28 25 21 19 41 44 27 28 32 31 18 20 36 37 34 35 39 41 5 1 16 14 26 27 11 15 29 28 42 46 12 11 47 44 31 29 48 49 45 49 23 20 12 10 47 50 23 25 31 33 1 3 25 26 38 41 36 40 15 ...
output:
0
result:
ok 1 number(s): "0"
Test #30:
score: 0
Accepted
time: 82ms
memory: 38684kb
input:
50 119 8 7 38 34 10 11 9 10 1 4 28 25 13 11 20 16 50 47 15 12 43 46 25 27 20 21 19 18 5 4 17 15 46 50 2 6 4 6 45 48 44 41 36 38 25 26 23 26 7 5 5 6 10 6 24 23 37 33 22 19 28 27 36 39 10 13 41 45 42 46 13 9 43 42 34 32 16 15 30 31 33 34 8 10 14 15 21 17 32 33 41 37 50 48 6 9 42 38 30 33 32 31 13 15 5...
output:
1
result:
ok 1 number(s): "1"
Test #31:
score: 0
Accepted
time: 51ms
memory: 25764kb
input:
50 189 11 14 29 28 47 45 49 47 7 11 32 30 33 31 18 17 42 40 23 19 19 20 18 20 24 21 28 27 24 28 16 18 12 8 12 11 41 44 15 18 16 12 13 14 5 3 18 22 34 38 15 16 29 30 20 17 25 23 38 39 48 44 27 31 42 46 36 35 21 20 8 6 32 28 6 7 24 20 32 36 25 24 20 16 6 9 9 7 8 7 36 39 46 48 35 33 41 45 43 41 28 31 5...
output:
1
result:
ok 1 number(s): "1"
Test #32:
score: 0
Accepted
time: 58ms
memory: 31172kb
input:
50 185 12 14 38 40 2 3 15 12 20 24 17 13 22 18 41 42 18 17 1 3 4 6 24 21 20 16 9 10 7 11 41 44 38 41 19 22 7 9 37 38 8 6 24 22 45 44 29 31 48 49 34 33 37 41 10 8 20 17 15 16 14 13 46 42 32 35 39 35 18 21 29 27 47 44 21 22 26 25 47 43 36 33 39 41 11 15 24 25 31 34 11 8 34 38 49 50 33 37 31 33 45 47 1...
output:
0
result:
ok 1 number(s): "0"
Test #33:
score: 0
Accepted
time: 47ms
memory: 33724kb
input:
50 180 35 37 43 44 8 4 24 27 13 9 38 41 34 29 31 28 17 19 41 44 37 33 45 40 9 6 21 17 48 49 3 7 19 20 13 10 17 12 31 35 6 7 7 2 2 3 6 4 31 27 40 35 20 21 6 2 27 23 47 43 21 16 5 4 19 14 28 33 28 32 44 39 47 46 27 22 1 5 17 16 46 48 48 50 44 46 15 18 35 34 13 17 24 20 41 37 24 21 49 45 47 48 5 10 49 ...
output:
1
result:
ok 1 number(s): "1"
Test #34:
score: 0
Accepted
time: 121ms
memory: 45400kb
input:
50 92 39 42 23 27 44 47 12 10 43 45 33 35 46 48 7 11 16 19 15 18 5 6 28 27 35 39 26 21 50 48 44 42 33 38 38 41 3 4 40 37 6 4 23 21 28 24 30 25 7 5 20 22 3 2 43 46 36 37 41 40 34 30 30 27 9 10 34 29 29 26 20 17 6 10 14 16 23 26 6 1 38 39 39 36 8 11 38 37 12 11 9 6 25 27 49 48 17 22 37 39 15 14 22 23 ...
output:
0
result:
ok 1 number(s): "0"
Test #35:
score: 0
Accepted
time: 48ms
memory: 31612kb
input:
50 222 46 41 44 41 23 19 21 18 19 15 9 11 11 10 36 41 15 11 39 42 23 25 4 1 17 21 40 45 32 33 33 31 24 29 22 23 17 16 32 30 18 17 45 41 12 15 24 27 21 24 26 24 29 27 42 45 6 11 25 24 29 25 18 15 4 3 38 33 47 49 8 5 49 46 21 25 30 25 32 35 45 47 14 13 47 50 19 17 19 16 11 7 38 37 9 4 45 44 35 39 31 3...
output:
0
result:
ok 1 number(s): "0"
Test #36:
score: 0
Accepted
time: 49ms
memory: 33508kb
input:
50 203 36 40 19 16 21 26 20 15 18 14 11 13 28 33 42 45 50 49 26 31 5 6 46 42 41 43 41 36 49 47 19 18 47 44 5 9 26 25 19 17 28 31 2 1 33 34 50 45 21 20 25 22 37 41 13 10 12 14 35 34 22 17 35 31 34 38 23 26 40 42 49 46 22 24 20 23 20 25 40 45 11 7 23 24 8 9 25 29 15 19 14 10 16 17 35 40 38 40 22 27 7 ...
output:
0
result:
ok 1 number(s): "0"
Test #37:
score: 0
Accepted
time: 50ms
memory: 31324kb
input:
50 203 18 16 45 50 28 24 4 3 28 29 13 18 16 12 25 20 29 30 36 39 44 39 31 28 28 23 40 38 28 26 21 18 40 45 13 15 15 18 49 46 36 41 48 47 16 20 42 47 37 40 24 25 8 10 7 8 3 7 6 5 44 41 48 44 30 34 45 43 16 15 12 17 30 26 19 16 31 36 10 15 42 40 9 10 39 38 49 50 24 27 34 31 34 33 8 5 6 1 35 34 25 27 7...
output:
1
result:
ok 1 number(s): "1"
Test #38:
score: -100
Time Limit Exceeded
input:
50 18 23 27 43 41 31 33 29 30 22 20 25 20 31 27 36 41 30 36 50 49 45 40 25 29 44 49 33 36 14 16 31 29 31 37 35 34