#include <bits/stdc++.h>
using namespace std;
vector<int> graph[109];
vector<pair<int, int> > tmove[109][109];
vector<vector<int> > moves;
vector<vector<int> > st;
int n, color[109], cnt[109];
bool inter[109];
void reset(){
for(int i=0; i<n; i++)
color[i] = i+1;
}
void make_move(){
vector<int> temp;
for(int i=0; i<n; i++)
temp.push_back(color[i]);
moves.push_back(temp);
st.push_back(temp);
}
void make_tmove(int d, int u, int v){
tmove[d][cnt[d]].push_back(make_pair(u, v));
}
void merge_moves(){
for(int d = 0; d <= 100; d++){
if(cnt[d] == 0)
break;
int mx = 0;
for(int i=0; i<tmove[d][0].size(); i++){
reset();
color[tmove[d][0][i].first] = color[tmove[d][0][i].second] = tmove[d][0][i].first +1;
make_move();
}
for(int i=0; i<tmove[d][105].size(); i++){
reset();
color[tmove[d][105][i].first] = color[tmove[d][105][i].second] = tmove[d][105][i].first +1;
make_move();
}
for(int i = 1; i <= cnt[d]; i++)
mx = max(mx, (int)tmove[d][i].size());
for(int i = 0; i < mx; i++){
reset();
for(int j = 1; j <= cnt[d]; j++){
if(tmove[d][j].size() >= i+1){
int s = tmove[d][j][i].first;
int e = tmove[d][j][i].second;
color[s] = color[e] = s+1;
}
}
make_move();
}
}
}
void answer(){
assert(moves.size() <= 20000);
printf("%d\n", moves.size());
for(vector<int> u: moves){
for(int v: u)
printf("%d ", v);
printf("\n");
}
}
vector<int> tree[109], child[109];
bool ch[109];
int par[109];
void dfs_span(int v){
ch[v] = 1;
for(int u: graph[v]){
if(!ch[u]){
tree[v].push_back(u);
tree[u].push_back(v);
child[v].push_back(u);
dfs_span(u);
par[u] = v;
}
}
}
vector<int> vertex;
void dfs(int c, int v, int d){
ch[v] = 1;
vertex.push_back(v);
for(int u: tree[v]){
if(!ch[u] && inter[u]){
if(v==c)
tmove[d][0].push_back(make_pair(v, u));
else
make_tmove(d, v, u);
dfs(c, u, d);
if(v==c)
tmove[d][105].push_back(make_pair(v, u));
else
make_tmove(d, u, v);
}
}
}
int getsize(int v){
ch[v] = 1;
int sz = 1;
for(int u: tree[v]){
if(!ch[u] && inter[u]){
sz += getsize(u);
}
}
return sz;
}
void solve(int d, vector<int> ver){
//printf("d=%d ver.sz=%d\n", d, ver.size());
if(ver.size() == 1)
return;
memset(inter, 0, sizeof(inter));
int c = -1, opt1 = 123523, i, j;
for(int u: ver){
inter[u] = 1;
}
for(int v: ver){
int mx = 0;
for(int u: tree[v]){
if(inter[u]){
memset(ch, 0, sizeof(ch));
ch[v] = 1;
mx = max(mx, getsize(u));
}
}
if(mx < opt1){
opt1 = mx;
c = v;
}
}
vector<pair<int, int> > vec;
for(int u: tree[c]){
if(inter[u]){
memset(ch, 0, sizeof(ch));
ch[c] = 1;
vec.push_back(make_pair(getsize(u), u));
}
}
sort(vec.begin(), vec.end(), [](pair<int, int> &u, pair<int, int> &v){return u>v;});
int sz = vec.size();
if(sz == 1){
make_tmove(d, c, vec[0].second);
return;
}
int cur = 0, tot = (int)ver.size() - 1, opt;
for(i=0; i<sz; i++){
cur += vec[i].first;
if(2*cur >= tot){
opt = i;
break;
}
}
if(2*cur - tot > tot - 2*(cur - vec[opt].first))
opt--;
assert(0 <= opt && opt+1 < vec.size());
vector<int> ver1;
vector<int> ver2;
memset(ch, 0, sizeof(ch));
for(i=opt+1; i<vec.size(); i++){
ch[vec[i].second] = 1;
}
vertex.clear();
cnt[d]++;
dfs(c, c, d);
ver1 = vertex;
memset(ch, 0, sizeof(ch));
for(i=0; i<=opt; i++){
ch[vec[i].second] = 1;
}
vertex.clear();
cnt[d]++;
dfs(c, c, d);
ver2 = vertex;
solve(d+1, ver1);
solve(d+1, ver2);
}
int main(){
int m, i, j, k, u, v;
scanf("%d %d", &n, &m);
for(i=1; i<=m; i++){
scanf("%d %d", &u, &v);
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs_span(0);
vector<int> ver;
for(i=0; i<n; i++)
ver.push_back(i);
solve(0, ver);
merge_moves();
answer();
return 0;
}
/*
for(i=1; i<n; i++){
for(k=0; k<n; k++){
color[k]= k+1;
}
bool ch[109] = {0, };
vector<int> vec;
for(j=0; j<n; j++){
if(!ch[j]){
for(int j2 = j; !ch[j2]; j2 = (j2 + i) % n){
//printf("j2=%d\n", j2);
vec.push_back(j2);
ch[j2]= 1;
}
}
}
for(k=0; k<n; k++){
color[k]= k+1;
}
for(j=0; j<vec.size()-1; j+=2){
color[vec[j]] = color[(vec[j] + i) % n] = vec[j]+1;
}
make_move();
make_move();
for(k=0; k<n; k++){
color[k]= k+1;
}
for(j=1; j<vec.size()-1; j+=2){
color[vec[j]] = color[(vec[j] + i) % n] = vec[j]+1;
}
make_move();
make_move();
for(k=0; k<n; k++){
color[k]= k+1;
}
for(j=vec.size()-1; j<=vec.size()-1; j+=2){
color[vec[j]] = color[(vec[j] + i) % n] = vec[j]+1;
}
make_move();
make_move();
}
answer();
return 0;
*/
Compilation message
Main.cpp: In function 'void merge_moves()':
Main.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i=0; i<tmove[d][0].size(); i++){
| ~^~~~~~~~~~~~~~~~~~~
Main.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i=0; i<tmove[d][105].size(); i++){
| ~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:43:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
43 | if(tmove[d][j].size() >= i+1){
| ~~~~~~~~~~~~~~~~~~~^~~~~~
Main.cpp: In function 'void answer()':
Main.cpp:55:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
55 | printf("%d\n", moves.size());
| ~^ ~~~~~~~~~~~~
| | |
| int std::vector<std::vector<int> >::size_type {aka long unsigned int}
| %ld
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from Main.cpp:1:
Main.cpp: In function 'void solve(int, std::vector<int>)':
Main.cpp:154:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | assert(0 <= opt && opt+1 < vec.size());
| ~~~~~~^~~~~~~~~~~~
Main.cpp:158:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(i=opt+1; i<vec.size(); i++){
| ~^~~~~~~~~~~
Main.cpp:112:32: warning: unused variable 'j' [-Wunused-variable]
112 | int c = -1, opt1 = 123523, i, j;
| ^
Main.cpp: In function 'int main()':
Main.cpp:177:12: warning: unused variable 'j' [-Wunused-variable]
177 | int m, i, j, k, u, v;
| ^
Main.cpp:177:15: warning: unused variable 'k' [-Wunused-variable]
177 | int m, i, j, k, u, v;
| ^
Main.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
178 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
180 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'void solve(int, std::vector<int>)':
Main.cpp:152:41: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
152 | if(2*cur - tot > tot - 2*(cur - vec[opt].first))
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
856 KB |
If people start at 0 and 1, then they can avoid each other |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
If people start at 0 and 1, then they can avoid each other |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
If people start at 0 and 1, then they can avoid each other |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
856 KB |
If people start at 0 and 1, then they can avoid each other |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
856 KB |
If people start at 0 and 1, then they can avoid each other |
| 2 |
Halted |
0 ms |
0 KB |
- |
