oj.uz

Submission #1058038

# Submission time Handle Problem Language Result Execution time Memory
1058038 2024-08-14T08:04:43 Z d(#11114) Infiltration (CCO24_day2problem1) C++17
17 / 25
 10 ms 856 KB 
#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=1e60;
			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]*d[i][j]*d[i][j]*d[i][j]*d[i][j]);
			for(int k: g[c[t][i]]){
				db s=1e60;
				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]*d[i][j]*d[i][j]*d[i][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
17.0 / 25.0

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