답안 #1058063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058063	2024-08-14T08:11:46 Z	d(#11114)	Infiltration (CCO24_day2problem1)	C++17	6 / 25	133 ms	604 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;
			for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) v+=d[c[t][i]][c[t^1][j]]*expl(d[i][j]);
			for(int k: g[c[t][i]]){
				db s=0;
				for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) s+=d[k][c[t^1][j]]*expl(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

6.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	116 ms	600 KB	Partially correct
2	Partially correct	84 ms	592 KB	Partially correct
3	Partially correct	87 ms	596 KB	Partially correct
4	Partially correct	115 ms	592 KB	Partially correct
5	Partially correct	116 ms	604 KB	Partially correct
6	Partially correct	133 ms	596 KB	Partially correct
7	Correct	3 ms	348 KB	Output is correct
8	Correct	3 ms	548 KB	Output is correct
9	Correct	4 ms	348 KB	Output is correct
10	Correct	4 ms	348 KB	Output is correct
11	Correct	3 ms	348 KB	Output is correct
12	Correct	3 ms	348 KB	Output is correct
13	Correct	3 ms	348 KB	Output is correct
14	Correct	3 ms	348 KB	Output is correct
15	Correct	3 ms	348 KB	Output is correct
16	Partially correct	34 ms	564 KB	Partially correct
17	Partially correct	31 ms	576 KB	Partially correct
18	Partially correct	35 ms	576 KB	Partially correct
19	Partially correct	38 ms	560 KB	Partially correct
20	Partially correct	40 ms	572 KB	Partially correct
21	Partially correct	42 ms	592 KB	Partially correct
22	Partially correct	41 ms	604 KB	Partially correct
23	Partially correct	44 ms	596 KB	Partially correct
24	Partially correct	107 ms	592 KB	Partially correct
25	Partially correct	112 ms	568 KB	Partially correct