Submission #1058072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1058072	2024-08-14T08:14:41 Z	d(#11114)	Infiltration (CCO24_day2problem1)	C++17	17 / 25	208 ms	596 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(1,(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(1,(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

17.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	198 ms	596 KB	Output is correct
2	Correct	161 ms	592 KB	Output is correct
3	Correct	160 ms	592 KB	Output is correct
4	Correct	208 ms	568 KB	Output is correct
5	Correct	204 ms	568 KB	Output is correct
6	Correct	201 ms	572 KB	Output is correct
7	Correct	4 ms	348 KB	Output is correct
8	Correct	5 ms	348 KB	Output is correct
9	Correct	4 ms	348 KB	Output is correct
10	Correct	5 ms	348 KB	Output is correct
11	Correct	5 ms	348 KB	Output is correct
12	Correct	5 ms	552 KB	Output is correct
13	Correct	5 ms	348 KB	Output is correct
14	Correct	5 ms	568 KB	Output is correct
15	Correct	5 ms	348 KB	Output is correct
16	Partially correct	64 ms	564 KB	Partially correct
17	Partially correct	60 ms	568 KB	Partially correct
18	Partially correct	58 ms	568 KB	Partially correct
19	Partially correct	64 ms	348 KB	Partially correct
20	Partially correct	67 ms	348 KB	Partially correct
21	Partially correct	76 ms	548 KB	Partially correct
22	Partially correct	67 ms	348 KB	Partially correct
23	Partially correct	72 ms	560 KB	Partially correct
24	Correct	184 ms	596 KB	Output is correct
25	Correct	188 ms	592 KB	Output is correct