Submission #1058074

# Submission time Handle Problem Language Result Execution time Memory
1058074 2024-08-14T08:14:58 Z d(#11114) Infiltration (CCO24_day2problem1) C++17
8 / 25
227 ms 600 KB
#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(2,(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(2,(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;
}
# Verdict Execution time Memory Grader output
1 Partially correct 217 ms 592 KB Partially correct
2 Partially correct 158 ms 592 KB Partially correct
3 Partially correct 160 ms 596 KB Partially correct
4 Partially correct 219 ms 596 KB Partially correct
5 Partially correct 222 ms 572 KB Partially correct
6 Partially correct 227 ms 560 KB Partially correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 4 ms 344 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 348 KB Output is correct
13 Correct 4 ms 556 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 59 ms 600 KB Partially correct
17 Partially correct 53 ms 564 KB Partially correct
18 Partially correct 59 ms 348 KB Partially correct
19 Partially correct 68 ms 552 KB Partially correct
20 Partially correct 68 ms 348 KB Partially correct
21 Partially correct 70 ms 560 KB Partially correct
22 Partially correct 68 ms 344 KB Partially correct
23 Partially correct 74 ms 564 KB Partially correct
24 Partially correct 193 ms 568 KB Partially correct
25 Partially correct 205 ms 564 KB Partially correct