QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#543349 | #9189. Make them Meet | zhoukangyang | 23 | 2ms | 3788kb | C++17 | 2.3kb | 2024-09-01 16:10:34 | 2024-09-01 16:10:36 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
#define pb emplace_back
using namespace std;
const int N = 107, mod = 998244353;
int n, m, tot;
vi e[N], G[N];
mt19937 rng;
int root, win;
int dfn[N], idt;
int fa[N];
int dep[N];
void dfs1(int x) {
dfn[x] = ++idt;
shuffle(e[x].begin(), e[x].end(), rng);
dep[x] = dep[fa[x]] + 1;
for(auto v : e[x]) {
if(!dfn[v]) {
fa[v] = x;
G[x].pb(v);
dfs1(v);
}
}
}
vector<vi>ans;
vi cur;
void dfs2(int x) {
for(auto v : G[x]) {
vi tmp(n);
L(i, 0, n - 1) tmp[i] = i;
tmp[v - 1] = tmp[x - 1];
ans.pb(tmp);
dfs2(v);
ans.pb(tmp);
}
}
int vis[N];
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
L(i, 1, m) {
int u, v;
cin >> u >> v;
++u;
++v;
e[u].pb(v);
e[v].pb(u);
}
if(m == n * (n - 1) / 2) {
cout << n << '\n';
L(i, 1, n) {
L(j, 1, n) cout << ((j + (i & 1)) / 2) << ' ';
cout << '\n';
}
return 0;
}
while(true) {
root = rng() % n + 1;
L(i, 1, n) dfn[i] = 0, G[i].clear();
L(i, 1, n) vis[i] = 0;
for(auto p : e[root])
vis[p] = 1;
idt = 0, fa[root] = 0;
dfs1(root);
int win = -1;
for(auto v : G[root]) {
int good = 1;
for(auto p : G[v])
good &= vis[p];
if(good) win = v;
}
if(win == -1) break;
}
R(d, n, 1) {
vi qwq(n);
L(i, 1, n) qwq[i - 1] = i;
L(i, 1, n) if(dep[i] <= d && (dep[i] - d) % 2 == 0) qwq[i - 1] = fa[i];
if(d % 2 == 0) {
qwq[root] = win;
}
ans.pb(qwq);
}
dfs2(root);
L(d, 1, n) {
vi qwq(n);
L(i, 1, n) qwq[i - 1] = i;
L(i, 1, n) if(dep[i] <= d && (dep[i] - d) % 2 == 0) qwq[i - 1] = fa[i];
if(d % 2 == 0) {
qwq[root] = win;
}
ans.pb(qwq);
}
R(d, n - 1, 1) {
vi qwq(n);
L(i, 1, n) qwq[i - 1] = i;
L(i, 1, n) if(dep[i] <= d && (dep[i] - d) % 2 == 0) qwq[i - 1] = fa[i];
if(d % 2 == 0) {
qwq[root] = win;
}
ans.pb(qwq);
}
cout << sz(ans) << '\n';
for(auto u : ans) {
for(auto v : u) cout << v << ' ';
cout << '\n';
}
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3564kb
input:
2 1 0 1
output:
2 1 1 0 1
result:
points 1.0
Test #2:
score: 10
Accepted
time: 0ms
memory: 3532kb
input:
3 2 0 1 0 2
output:
12 1 1 0 3 2 3 1 2 0 2 1 2 0 0 2 0 0 2 2 1 2 1 2 0 3 2 3 1 1 0 3 2 3 1 2 0
result:
points 1.0
Test #3:
score: 10
Accepted
time: 0ms
memory: 3788kb
input:
4 3 0 1 0 2 0 3
output:
17 3 2 3 0 1 1 0 1 3 2 3 0 1 2 0 4 2 1 2 3 0 1 2 0 0 1 2 0 0 0 2 3 0 0 2 3 2 1 2 3 1 2 0 4 3 2 3 0 1 1 0 1 3 2 3 0 1 1 0 1 3 2 3 0 1 2 0 4
result:
points 1.0
Test #4:
score: 10
Accepted
time: 0ms
memory: 3744kb
input:
99 98 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 58 0 59 0 60 0 6...
output:
492 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 84 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ...
result:
points 1.0
Test #5:
score: 10
Accepted
time: 2ms
memory: 3732kb
input:
100 99 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 58 0 59 0 60 0 ...
output:
497 13 2 3 4 5 6 7 8 9 10 11 12 13 0 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 1...
result:
points 1.0
Subtask #2:
score: 13
Accepted
Test #6:
score: 13
Accepted
time: 0ms
memory: 3716kb
input:
2 1 0 1
output:
2 1 1 0 1
result:
points 1.0
Test #7:
score: 13
Accepted
time: 0ms
memory: 3488kb
input:
3 3 1 2 0 1 0 2
output:
3 1 1 2 0 1 1 1 1 2
result:
points 1.0
Test #8:
score: 13
Accepted
time: 0ms
memory: 3472kb
input:
4 6 0 1 0 3 2 3 0 2 1 3 1 2
output:
4 1 1 2 2 0 1 1 2 1 1 2 2 0 1 1 2
result:
points 1.0
Test #9:
score: 13
Accepted
time: 0ms
memory: 3780kb
input:
10 45 4 9 2 8 5 9 1 2 2 9 4 5 5 7 6 7 1 3 1 9 3 4 0 3 4 7 0 6 5 6 7 9 4 8 6 8 0 5 1 8 3 9 1 6 6 9 4 6 0 8 2 3 0 4 0 9 0 7 3 6 0 2 2 5 3 7 3 5 7 8 5 8 8 9 0 1 2 7 1 7 1 4 2 6 2 4 3 8 1 5
output:
10 1 1 2 2 3 3 4 4 5 5 0 1 1 2 2 3 3 4 4 5 1 1 2 2 3 3 4 4 5 5 0 1 1 2 2 3 3 4 4 5 1 1 2 2 3 3 4 4 5 5 0 1 1 2 2 3 3 4 4 5 1 1 2 2 3 3 4 4 5 5 0 1 1 2 2 3 3 4 4 5 1 1 2 2 3 3 4 4 5 5 0 1 1 2 2 3 3 4 4 5
result:
points 1.0
Test #10:
score: 13
Accepted
time: 0ms
memory: 3484kb
input:
15 105 4 10 8 13 0 12 11 12 2 13 8 14 6 10 0 4 8 12 2 12 1 13 5 9 2 8 7 10 6 13 0 13 9 13 7 11 3 13 0 3 4 7 5 13 7 13 0 7 0 11 0 8 0 2 2 4 2 6 6 9 0 1 9 11 1 9 3 14 3 4 10 11 5 10 0 9 3 9 6 11 2 10 5 6 2 5 1 14 6 8 9 12 2 11 9 10 5 12 5 14 4 14 7 14 5 8 5 7 1 12 0 14 7 9 3 11 1 8 0 10 1 3 8 9 4 6 10...
output:
15 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 0 1 1 2 2 3 3 4 4 ...
result:
points 1.0
Test #11:
score: 13
Accepted
time: 0ms
memory: 3592kb
input:
30 435 5 6 8 11 3 26 8 29 10 22 6 20 18 22 23 27 13 18 2 26 21 25 11 15 25 28 2 22 18 20 3 13 10 19 6 29 10 15 0 13 7 22 13 28 9 16 2 28 6 16 3 17 6 14 4 8 16 17 9 22 22 24 26 29 14 28 19 29 28 29 4 28 13 23 12 19 1 2 5 10 1 6 2 4 25 27 4 22 9 26 16 23 5 16 6 11 0 17 16 27 0 7 15 26 2 16 8 12 1 25 3...
output:
30 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 1 1 2 2...
result:
points 1.0
Test #12:
score: 13
Accepted
time: 1ms
memory: 3744kb
input:
40 780 21 24 11 32 12 27 19 20 3 35 25 35 32 35 27 33 0 24 1 3 1 29 14 25 8 30 24 31 14 32 7 12 5 31 28 35 7 10 18 24 13 32 1 26 3 4 10 30 14 38 22 24 9 31 5 10 17 32 2 34 28 39 3 38 13 34 6 10 0 6 9 25 11 14 13 20 10 20 18 28 6 33 34 35 29 33 16 39 4 38 3 24 20 29 17 18 33 36 13 37 24 27 12 33 5 29...
output:
40 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19...
result:
points 1.0
Test #13:
score: 13
Accepted
time: 0ms
memory: 3560kb
input:
50 1225 6 10 14 36 0 34 7 23 22 31 18 34 2 19 13 21 0 46 0 11 2 43 2 11 13 20 13 19 7 39 35 37 9 17 31 38 13 40 7 28 2 41 20 46 25 36 12 39 1 37 21 42 33 48 10 24 13 26 26 37 0 47 17 19 1 28 28 40 15 40 11 22 10 19 24 28 12 28 19 40 6 12 13 48 20 37 11 46 8 19 5 24 16 28 15 47 31 34 11 21 28 33 14 1...
output:
50 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 ...
result:
points 1.0
Test #14:
score: 13
Accepted
time: 1ms
memory: 3676kb
input:
100 4950 24 39 27 46 11 71 57 65 3 8 84 97 74 87 17 49 12 72 1 4 22 83 29 42 28 65 39 89 29 92 26 78 45 53 18 44 33 43 14 98 50 66 21 95 32 67 21 33 21 80 59 77 70 85 13 16 0 41 31 65 51 80 22 80 30 79 55 75 54 82 29 57 72 97 31 85 86 87 60 90 1 17 65 81 13 15 44 71 58 88 65 87 8 31 77 99 4 44 29 43...
output:
100 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 0 1 1 2 2 3 3...
result:
points 1.0
Subtask #3:
score: 0
Wrong Answer
Test #15:
score: 11
Accepted
time: 0ms
memory: 3544kb
input:
2 1 0 1
output:
2 1 1 0 1
result:
points 1.0
Test #16:
score: 11
Accepted
time: 0ms
memory: 3484kb
input:
3 2 0 1 1 2
output:
12 2 2 0 1 3 3 1 2 0 0 2 2 1 1 2 1 1 2 0 2 2 1 2 0 1 3 3 2 2 0 1 3 3 1 2 0
result:
points 1.0
Test #17:
score: 11
Accepted
time: 0ms
memory: 3540kb
input:
4 3 0 1 1 2 2 3
output:
17 1 0 3 3 0 2 2 4 1 0 3 4 0 2 3 4 0 0 2 3 0 1 1 3 0 1 2 2 0 1 2 2 0 1 1 3 0 0 2 3 0 2 3 4 1 0 3 4 0 2 2 4 1 0 3 3 0 2 2 4 1 0 3 4 0 2 3 4
result:
points 1.0
Test #18:
score: 0
Wrong Answer
time: 1ms
memory: 3632kb
input:
49 48 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48
output:
242 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 0 45 45 47 47 49 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 0 46 46 48 48 1 3 3 5 5 7 7 9 9 1...
result:
wrong answer If people start at 0 and 44, then they can avoid each other
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%