Submission #1058033

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1058033	2024-08-14T08:03:23 Z	d(#11114)	Infiltration (CCO24_day2problem1)	C++17	17 / 25	41 ms	664 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=exp(101);
			for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) v=min(v,(db)d[c[t][i]][c[t^1][j]]*exp(d[i][j]));
			for(int k: g[c[t][i]]){
				db s=exp(101);
				for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) s=min(s,(db)d[k][c[t^1][j]]*exp(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

17.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	30 ms	640 KB	Partially correct
2	Correct	24 ms	656 KB	Output is correct
3	Correct	22 ms	604 KB	Output is correct
4	Correct	29 ms	660 KB	Output is correct
5	Correct	35 ms	664 KB	Output is correct
6	Correct	31 ms	644 KB	Output is correct
7	Correct	1 ms	564 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	1 ms	556 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	3 ms	348 KB	Output is correct
14	Correct	3 ms	556 KB	Output is correct
15	Correct	3 ms	348 KB	Output is correct
16	Partially correct	10 ms	608 KB	Partially correct
17	Partially correct	15 ms	588 KB	Partially correct
18	Partially correct	12 ms	604 KB	Partially correct
19	Partially correct	11 ms	604 KB	Partially correct
20	Partially correct	10 ms	604 KB	Partially correct
21	Partially correct	10 ms	564 KB	Partially correct
22	Partially correct	15 ms	604 KB	Partially correct
23	Partially correct	11 ms	564 KB	Partially correct
24	Correct	41 ms	628 KB	Output is correct
25	Correct	27 ms	656 KB	Output is correct