oj.uz

답안 #256486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256486 2020-08-02T18:28:49 Z amiratou Mag (COCI16_mag) C++14
120 / 120
 728 ms 111624 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF (int)(1e18)
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
const int MX = 1000006;
vii vec[MX];
int val[MX],two,one;
int solve(int node,int p){
	v g;
	for(auto &it:vec[node])
		if(it.fi!=p && (val[it.fi]==1)){
			if(it.se==-1)it.se=solve(it.fi,node);
			g.pb(it.se);
		}
	sort(all(g),greater<int>());
	if((node==p) && (val[node]==2) && (sz(g)>=2))two=max(two,g[0]+g[1]+1);
	if((node==p) && (val[node]==1) && (sz(g)>=1))one=max(one,g[0]+1);
	return ((sz(g)?g[0]:0)+(val[node]==1))*(val[node]==1);
}
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	ii ans={INF,1};
	int n,a,b;
	cin>>n;
	for (int i = 0; i < n-1; ++i)
	{
		cin>>a>>b;
		a--,b--;
		vec[a].pb({b,-1});
		vec[b].pb({a,-1});
	}
	for (int i = 0; i < n; ++i){
		cin>>val[i];
		if(val[i]<ans.fi)ans.fi=val[i];
	}
	for (int i = 0; i < n; ++i)
		solve(i,i);
	if(one || two){
		if(!two)ans={1,one};
		else{
			if((2*one)>=two)ans={1,one};
			else ans={2,two};
		}
	}
	int g=__gcd(ans.fi,ans.se);
	cout<<ans.fi/g<<"/"<<ans.se/g<<"\n";
	return 0;
}

//do smth instead of nothing and stay organized
//long long
//array bounds
//special cases
//binary search

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 19 ms 23808 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 16 ms 23936 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 565 ms 111624 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 508 ms 78072 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 582 ms 79416 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 593 ms 78388 KB Output is correct
2 Correct 439 ms 63992 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 460 ms 84944 KB Output is correct
2 Correct 142 ms 29848 KB Output is correct
3 Correct 629 ms 78708 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 29800 KB Output is correct
2 Correct 635 ms 79192 KB Output is correct
3 Correct 728 ms 53500 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 558 ms 75088 KB Output is correct
2 Correct 638 ms 77812 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 603 ms 78968 KB Output is correct
2 Correct 649 ms 53624 KB Output is correct