답안 #1058036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058036	2024-08-14T08:03:49 Z	d(#11114)	Infiltration (CCO24_day2problem1)	C++17	17 / 25	44 ms	660 KB

Main

#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(200);
			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(200);
				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;
}

Subtask #1

17.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	604 KB	Output is correct
2	Correct	36 ms	600 KB	Output is correct
3	Correct	26 ms	632 KB	Output is correct
4	Correct	31 ms	644 KB	Output is correct
5	Correct	28 ms	660 KB	Output is correct
6	Correct	30 ms	604 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	3 ms	348 KB	Output is correct
10	Correct	2 ms	560 KB	Output is correct
11	Correct	3 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	2 ms	344 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Partially correct	9 ms	600 KB	Partially correct
17	Partially correct	8 ms	564 KB	Partially correct
18	Partially correct	8 ms	604 KB	Partially correct
19	Partially correct	11 ms	604 KB	Partially correct
20	Partially correct	10 ms	584 KB	Partially correct
21	Partially correct	11 ms	604 KB	Partially correct
22	Partially correct	12 ms	564 KB	Partially correct
23	Partially correct	11 ms	608 KB	Partially correct
24	Correct	25 ms	620 KB	Output is correct
25	Correct	44 ms	660 KB	Output is correct