답안 #1058034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058034	2024-08-14T08:03:41 Z	d(#11114)	Infiltration (CCO24_day2problem1)	C++17	17 / 25	43 ms	640 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(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;
}

Subtask #1

17.0 / 25.0

#	결과	실행 시간	메모리	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