Submission #1058018

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1058018	2024-08-14T08:00:22 Z	d(#11114)	Infiltration (CCO24_day2problem1)	C++17	15 / 25	9 ms	668 KB

Main

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll=long long;
using db=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=1e9;
			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]]*d[i][j]);
			for(int k: g[c[t][i]]){
				db s=1e9;
				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]]*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

15.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	6 ms	604 KB	Partially correct
2	Correct	5 ms	640 KB	Output is correct
3	Partially correct	7 ms	604 KB	Partially correct
4	Partially correct	6 ms	604 KB	Partially correct
5	Partially correct	6 ms	668 KB	Partially correct
6	Partially correct	6 ms	604 KB	Partially correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	2 ms	344 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	2 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Partially correct	2 ms	604 KB	Partially correct
17	Partially correct	2 ms	604 KB	Partially correct
18	Partially correct	2 ms	600 KB	Partially correct
19	Partially correct	2 ms	604 KB	Partially correct
20	Partially correct	2 ms	604 KB	Partially correct
21	Partially correct	2 ms	604 KB	Partially correct
22	Partially correct	2 ms	604 KB	Partially correct
23	Partially correct	2 ms	604 KB	Partially correct
24	Partially correct	5 ms	612 KB	Partially correct
25	Partially correct	9 ms	600 KB	Partially correct