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

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(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;
}

Subtask #1

8.0 / 25.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