oj.uz

답안 #1057998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057998 2024-08-14T07:54:35 Z d(#11114) Infiltration (CCO24_day2problem1) C++17
8 / 25
 6 ms 688 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],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],v=0;
			for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) v=max(v,d[c[t][i]][c[t^1][j]]);
			for(int k: g[c[t][i]]){
				int s=0;
				for(int j=1;j<=n;j++) if(t==0?f[i][j]:f[j][i]) s=max(s,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
8.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 6 ms 604 KB Partially correct
2 Partially correct 3 ms 604 KB Partially correct
3 Partially correct 3 ms 640 KB Partially correct
4 Partially correct 5 ms 604 KB Partially correct
5 Partially correct 4 ms 604 KB Partially correct
6 Partially correct 5 ms 688 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 1 ms 344 KB Output is correct
12 Correct 1 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 348 KB Output is correct
16 Partially correct 1 ms 604 KB Partially correct
17 Partially correct 2 ms 600 KB Partially correct
18 Partially correct 2 ms 600 KB Partially correct
19 Partially correct 2 ms 552 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 616 KB Partially correct
23 Partially correct 2 ms 604 KB Partially correct
24 Partially correct 5 ms 604 KB Partially correct
25 Partially correct 5 ms 600 KB Partially correct