제출 #1252508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252508		DangKhoizzzz	Mag (COCI16_mag)	C++20	120 / 120	527 ms	111476 KiB

mag

/*

cao nhat 2 tplt toan value 1 

-> tu = 1/2 



*/



#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 1e6 + 2;
vector < ll > adj[N];
ll c[N];
ll used[N] = {0}, dist[N] = {0}, mx_dist[N] = {0};
ll furthest_node, furthest_path;
void Go(ll node, ll par) {
	used[node] = 1;
	if ( dist[node] >= furthest_path) {
		furthest_path = dist[node];
		furthest_node = node;
	}
	for ( ll chi : adj[node]) {
		if ( chi == par) continue;
		dist[chi] = dist[node] + 1;
		Go(chi, node);
		dist[chi] = 0;
	}
}
void Update(ll node, ll par) {
	mx_dist[node] = max(mx_dist[node], dist[node]);
	for ( ll chi : adj[node]) {
		if ( chi == par) continue;
		dist[chi] = dist[node] + 1;
		Update(chi, node);
		dist[chi] = 0;
	}
}

int main() {
	ll n, m, r, i, j,cnt, ans, t, mn = 1e18;

	cin >> n;
	ll x[n + 2], y[n + 2];
	for (i = 1; i < n; i++) {
		cin >> x[i] >> y[i];
	}	
	
	for (i = 1; i <= n; i ++) {
		cin >> c[i];
		mn = min(mn, c[i]);
	}
	
	if (mn > 1) {
		cout << mn <<"/1" << endl;
		return 0;
	}
	
	for (i = 1; i < n; i ++) {
		if ( c[x[i]] == 1 && c[y[i]] == 1) {
			adj[x[i]].push_back(y[i]);
			adj[y[i]].push_back(x[i]);
		}
	}	
	for (i = 1; i <= n; i ++) mx_dist[i] = -2;
	ans = 0;
	for (i = 1; i <= n; i ++) {
		if ( c[i] != 1) continue;
		if ( used[i] == 0) {
			furthest_node = furthest_path = 0;
			Go(i, i);
			r =  furthest_node ;
			furthest_node = furthest_path = 0;
			Go(r , r);
			Update(r, r);
			Update(furthest_node, furthest_node);
			
			ans = max(ans, furthest_path);
		}
	}
	
	
	ans ++;
	for (i = 1; i <= n; i ++) adj[i].clear();
	for (i = 1; i < n; i ++) {
		adj[x[i]].push_back(y[i]);
		adj[y[i]].push_back(x[i]);
	}
	for (i = 1; i <= n; i++) {
		if ( c[i] != 2) continue;
		cnt= 0;
		for(ll X : adj[i]) {
			if ( mx_dist[X] + 1 == ans) cnt ++;
		}
		if ( cnt > 1) {
			cout << "2/" << ans * 2 + 1 << endl;
			return 0;
		}
	}
	cout <<"1/"<< ans << endl;
	
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12