#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll=long long;
using db=long double;
using pii=array<int,2>;
using tii=array<int,3>;
using ti4=array<int,4>;
const int N=105;
int n,vis[N],d[N][N],c[2][N],f[N][N],m;
vector<int> g[N],ans[2][N];
void dfs(int u,int p,int r){
for(int v: g[u]) if(p!=v){
d[r][v]=d[r][u]+1;
dfs(v,u,r);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int u,v,i=1;i<n;i++){
cin>>u>>v;
u++; v++;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++) dfs(i,0,i);
for(int i=1;i<=n;i++){
c[0][i]=c[1][i]=i;
for(int j=1;j<=n;j++) if(i!=j) f[i][j]=1;
}
m=n*(n-1);
for(int t=0;m;t^=1){
debug(t,m);
for(int i=1;i<=n;i++){
int u=c[t][i];
db v=exp(101);
for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) v=min(v,(db)d[c[t][i]][c[t^1][j]]*exp(d[i][j]));
for(int k: g[c[t][i]]){
db s=exp(101);
for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) s=min(s,(db)d[k][c[t^1][j]]*exp(d[i][j]));
if(s<v){
v=s;
u=k;
}
}
c[t][i]=u;
for(int j=1;j<=n;j++) if(c[t][i]==c[t^1][j]){
if(t==0&&f[i][j]){
f[i][j]=0;
m--;
}
if(t==1&&f[j][i]){
f[j][i]=0;
m--;
}
}
ans[0][i].push_back(c[0][i]);
ans[1][i].push_back(c[1][i]);
}
}
cout<<ans[0][1].size()<<"\n";
for(int i=1;i<=n;i++){
for(int x: ans[0][i]) cout<<x-1<<" ";
cout<<"\n";
}
for(int i=1;i<=n;i++){
for(int x: ans[1][i]) cout<<x-1<<" ";
cout<<"\n";
}
double res=0;
for(int u=1;u<=n;u++) for(int v=1;v<=n;v++) if(u!=v){
int t=0;
while(ans[0][u][t]!=ans[1][v][t]) t++;
t++;
if((double)t/d[u][v]>=100) debug((double)t/d[u][v],u,v,t,d[u][v]);
res=max(res,(double)t/d[u][v]);
}
debug(res);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
640 KB |
Output is correct |
| 2 |
Correct |
21 ms |
604 KB |
Output is correct |
| 3 |
Correct |
21 ms |
604 KB |
Output is correct |
| 4 |
Correct |
28 ms |
600 KB |
Output is correct |
| 5 |
Correct |
35 ms |
604 KB |
Output is correct |
| 6 |
Correct |
30 ms |
640 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
2 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
372 KB |
Output is correct |
| 10 |
Correct |
3 ms |
404 KB |
Output is correct |
| 11 |
Correct |
2 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
3 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
2 ms |
348 KB |
Output is correct |
| 16 |
Partially correct |
9 ms |
604 KB |
Partially correct |
| 17 |
Partially correct |
8 ms |
600 KB |
Partially correct |
| 18 |
Partially correct |
9 ms |
616 KB |
Partially correct |
| 19 |
Partially correct |
11 ms |
604 KB |
Partially correct |
| 20 |
Partially correct |
10 ms |
604 KB |
Partially correct |
| 21 |
Partially correct |
10 ms |
604 KB |
Partially correct |
| 22 |
Partially correct |
11 ms |
612 KB |
Partially correct |
| 23 |
Partially correct |
10 ms |
612 KB |
Partially correct |
| 24 |
Correct |
27 ms |
604 KB |
Output is correct |
| 25 |
Correct |
43 ms |
612 KB |
Output is correct |
