Submission #1058081

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1058081	2024-08-14T08:19:12 Z	d(#11114)	Infiltration (CCO24_day2problem1)	C++17	25 / 25	12 ms	856 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){
		for(int i=1;i<=n;i++){
			int u=c[t][i];
			pii v{10000,10000};
			for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) v=min(v,{d[i][j],d[c[t][i]][c[t^1][j]]});
			for(int k: g[c[t][i]]){
				pii s{10000,10000};
				for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) s=min(s,{d[i][j],d[k][c[t^1][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

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	604 KB	Output is correct
2	Correct	10 ms	604 KB	Output is correct
3	Correct	5 ms	600 KB	Output is correct
4	Correct	7 ms	604 KB	Output is correct
5	Correct	7 ms	604 KB	Output is correct
6	Correct	7 ms	604 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 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	Correct	2 ms	604 KB	Output is correct
17	Correct	2 ms	604 KB	Output is correct
18	Correct	2 ms	604 KB	Output is correct
19	Correct	4 ms	604 KB	Output is correct
20	Correct	3 ms	604 KB	Output is correct
21	Correct	5 ms	564 KB	Output is correct
22	Correct	5 ms	856 KB	Output is correct
23	Correct	3 ms	604 KB	Output is correct
24	Correct	6 ms	640 KB	Output is correct
25	Correct	7 ms	600 KB	Output is correct