QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#314157 | #7303. City United | zdczdc | TL | 657ms | 4860kb | C++20 | 1.1kb | 2024-01-25 13:36:36 | 2024-01-25 13:36:37 |
Judging History
answer
#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[(r) + 1]
using namespace std;
void file(){
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
}
using ll = long long;
const int sMax = 4'782'969;
int n, m;
array<int, 16> pw;
array<vector<int>, 55> g;
bitset<sMax> f, tf;
int main(){
// file();
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
pw[0] = 1;
for(int i = 1; i <= 15; i++) pw[i] = 3 * pw[i - 1];
for(int i = 1, u, v; i <= m; i++){
cin >> u >> v;
if(u < v) swap(u, v);
g[u].push_back(v);
}
tf[0] = 1;
bool rs = 0;
auto xor1 = [&](auto &s, int x){ s[x] = s[x] ^ 1; };
for(int i = 0; i <= n; i++, tf = f){
f.reset();
for(int S = 0; S < sMax; S++){
if(!tf[S]) continue;
if((S % 3) == 1) rs ^= 1;
vector<int> cnt(3, 0);
for(int to : g[i + 1]) cnt[(S / pw[i - to]) % 3]++;
if(!cnt[2]) xor1(f, (S * 3 + 1) % sMax);
if(!cnt[1]) xor1(f, (S * 3 + 2) % sMax);
xor1(f, (S * 3) % sMax);
}
}
cout << rs << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 18ms
memory: 4792kb
input:
3 2 1 2 2 3
output:
0
result:
ok 1 number(s): "0"
Test #2:
score: 0
Accepted
time: 18ms
memory: 4844kb
input:
3 3 1 2 2 3 3 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 67ms
memory: 4844kb
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: 70ms
memory: 4860kb
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: 67ms
memory: 4708kb
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: 71ms
memory: 4780kb
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: 4752kb
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: 71ms
memory: 4852kb
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: 72ms
memory: 4768kb
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: 71ms
memory: 4756kb
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: 67ms
memory: 4792kb
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: 70ms
memory: 4792kb
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: 627ms
memory: 4776kb
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: 408ms
memory: 4840kb
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: 585ms
memory: 4804kb
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: 351ms
memory: 4732kb
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: 357ms
memory: 4848kb
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: 366ms
memory: 4756kb
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: 255ms
memory: 4716kb
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: 281ms
memory: 4772kb
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: 286ms
memory: 4736kb
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: 261ms
memory: 4732kb
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: 247ms
memory: 4748kb
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: 657ms
memory: 4816kb
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: 262ms
memory: 4800kb
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: 259ms
memory: 4800kb
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: 243ms
memory: 4852kb
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: 234ms
memory: 4792kb
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: 242ms
memory: 4852kb
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: 253ms
memory: 4844kb
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: 229ms
memory: 4800kb
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: 259ms
memory: 4724kb
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: 228ms
memory: 4792kb
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: 251ms
memory: 4720kb
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: 248ms
memory: 4804kb
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: 230ms
memory: 4792kb
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: 224ms
memory: 4720kb
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