oj.uz

답안 #1057858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057858 2024-08-14T06:52:16 Z d(#11114) Infiltration (CCO24_day2problem1) C++17
6 / 25
 1 ms 604 KB 
#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],sz[N];
vector<int> g[N],ans[2][N];
void dfsSize(int u,int p){
	sz[u]=1;
	for(int v: g[u]) if(p!=v&&!vis[v]){
		dfsSize(v,u);
		sz[u]+=sz[v];
	}
}
int findCentroid(int u,int p,int S){
	for(int v: g[u]) if(p!=v&&!vis[v]&&sz[v]>=S) return findCentroid(v,u,S);
	return u;
}
int p[N][N];
vector<int> C[N];
void initPar(int u,int r){
	for(int v: g[u]) if(p[r][u]!=v&&!vis[v]){
		p[r][v]=u;
		initPar(v,r);
	}
}
int solve(int u){
	dfsSize(u,0);
	u=findCentroid(u,0,(sz[u]+1)/2);
	initPar(u,u);
	vis[u]=1;
	vector<int> V;
	for(int v: g[u]) if(!vis[v]) V.push_back(solve(v));
	for(int v: V){
		int w=v;
		while(u!=w){
			w=p[u][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[u].push_back(u);
	for(int v: V) for(int w: C[v]) C[u].push_back(w);
	int t=2;
	for(int v: C[u]) t=max(t,(int)ans[0][v].size());
	t=(t+1)/2*2;
	for(int v: C[u]) while((int)ans[0][v].size()<t){
		ans[0][v].push_back(u);
		ans[1][v].push_back(u);
	}
	return u;
}
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++) sort(g[i].begin(),g[i].end());
	int c=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";
		assert(ans[0][i].size()==ans[0][1].size());
		for(int x: ans[0][i]) assert(1<=x&&x<=n);
		assert(ans[0][i].back()==c);
	}
	for(int i=1;i<=n;i++){
		for(int x: ans[1][i]) cout<<x-1<<" ";
		cout<<"\n";
		assert(ans[1][i].size()==ans[0][1].size());
		for(int x: ans[1][i]) assert(1<=x&&x<=n);
		assert(ans[1][i].back()==c);
	}
	return 0;
}

Subtask #1
6.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 600 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 0 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 1 ms 344 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 348 KB Output is correct
16 Partially correct 1 ms 604 KB Partially correct
17 Partially correct 1 ms 348 KB Partially correct
18 Partially correct 0 ms 604 KB Partially correct
19 Partially correct 0 ms 604 KB Partially correct
20 Partially correct 1 ms 604 KB Partially correct
21 Partially correct 1 ms 604 KB Partially correct
22 Partially correct 1 ms 344 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