답안 #1058069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058069	2024-08-14T08:14:26 Z	d(#11114)	Infiltration (CCO24_day2problem1)	C++17	6 / 25	230 ms	600 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=0;
			vector<db> V;
			for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) V.push_back(d[c[t][i]][c[t^1][j]]*expl(d[i][j]));
			sort(V.begin(),V.end());
			for(int i=0;i<min(10,(int)V.size());i++) v+=V[i];
			for(int k: g[c[t][i]]){
				db s=0;
				vector<db> V;
				for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) V.push_back(d[k][c[t^1][j]]*expl(d[i][j]));
				sort(V.begin(),V.end());
				for(int i=0;i<min(10,(int)V.size());i++) s+=V[i];
				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

6.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	212 ms	592 KB	Partially correct
2	Partially correct	152 ms	592 KB	Partially correct
3	Partially correct	150 ms	552 KB	Partially correct
4	Partially correct	207 ms	592 KB	Partially correct
5	Partially correct	220 ms	600 KB	Partially correct
6	Partially correct	230 ms	596 KB	Partially correct
7	Correct	4 ms	348 KB	Output is correct
8	Correct	4 ms	348 KB	Output is correct
9	Correct	4 ms	348 KB	Output is correct
10	Correct	4 ms	348 KB	Output is correct
11	Correct	4 ms	348 KB	Output is correct
12	Correct	4 ms	560 KB	Output is correct
13	Correct	4 ms	348 KB	Output is correct
14	Correct	4 ms	348 KB	Output is correct
15	Correct	4 ms	348 KB	Output is correct
16	Partially correct	54 ms	568 KB	Partially correct
17	Partially correct	49 ms	564 KB	Partially correct
18	Partially correct	49 ms	348 KB	Partially correct
19	Partially correct	55 ms	348 KB	Partially correct
20	Partially correct	57 ms	344 KB	Partially correct
21	Partially correct	60 ms	552 KB	Partially correct
22	Partially correct	76 ms	548 KB	Partially correct
23	Partially correct	67 ms	592 KB	Partially correct
24	Partially correct	183 ms	592 KB	Partially correct
25	Partially correct	195 ms	564 KB	Partially correct