Submission #1057963

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1057963	2024-08-14T07:41:05 Z	d(#11114)	Infiltration (CCO24_day2problem1)	C++17	6 / 25	1 ms	604 KB

Main

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll=long long;
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];
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 p[N][N];
vector<int> V,C[N];
void dfs2(int u,int p){
	V.push_back(u);
	for(int v: g[u]) if(p!=v&&!vis[v]) dfs2(v,u);
}
void dfs3(int u,int r){
	for(int v: g[u]) if(p[r][u]!=v&&!vis[v]){
		p[r][v]=u;
		dfs3(v,r);
	}
}
int solve(int r){
	V.clear();
	dfs2(r,0);
	vector<int> L=V;
	r=0;
	int val=1e9;
	for(int u: L){
		int di=0;
		for(int v: L) di=max(di,d[u][v]);
		if(di<val){
			val=di;
			r=u;
		}
	}
	dfs3(r,r);
	vis[r]=1;
	vector<int> V;
	for(int v: g[r]) if(!vis[v]) V.push_back(solve(v));
	for(int v: V){
		int w=v;
		while(r!=w){
			w=p[r][w];
			for(int x: C[v]){
				ans[0][x].push_back(w);
				ans[0][x].push_back(w);
				ans[1][x].push_back(ans[1][x].back());
				ans[1][x].push_back(w);
			}
		}
	}
	C[r].push_back(r);
	for(int v: V) for(int w: C[v]) C[r].push_back(w);
	int t=2;
	for(int v: C[r]) t=max(t,(int)ans[0][v].size());
	t=(t+1)/2*2;
	for(int v: C[r]) while((int)ans[0][v].size()<t){
		ans[0][v].push_back(r);
		ans[1][v].push_back(r);
	}
	return 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);
	solve(1);
	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

6.0 / 25.0

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