제출 #1251548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251548		nguyenkhangninh99	Mag (COCI16_mag)	C++20	120 / 120	499 ms	127184 KiB

mag

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int maxn = 1e6 + 5;

vector<int> adj[maxn];      
vector<int> a, id, chain;         

void bfs(int st, vector<int>& node) {
    queue<int> q;
    q.push(st);
    id[st] = st; 
    node.push_back(st);
    while(!q.empty()){
        int u = q.front(); 
        q.pop();
        for (int v : adj[u]) {
            if(a[v] == 1 && id[v] == 0){
                id[v] = st;
                node.push_back(v);
                q.push(v);
            }
        }
    }
}
 
void bfs_distance(int st, unordered_map<int, int>& d) {
    queue<int> q;
    q.push(st);
    d[st] = 0;
    while(!q.empty()){
        int u = q.front(); 
        q.pop();
        for(int v: adj[u]){
            if(a[v] == 1 && d.find(v) == d.end() && id[v] == id[st]){
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
}
 
bool smaller(pair<int, int> x, pair<int, int> y){
    return x.first * y.second < y.first * x.second;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    for (int i = 1; i <= n - 1; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    a.resize(n + 1);
    id.assign(n + 1, 0); 
    chain.assign(n + 1, 1);

    for(int i = 1; i <= n; i++) cin >> a[i];
    
    pair<int, int> res = {*min_element(a.begin() + 1, a.end()), 1}; 
    
    int diam = 0; 
    for (int i = 1; i <= n; i++){
        if(id[i] || a[i] != 1) continue;
        vector<int> node;
        bfs(i, node);
        if(node.size() >= 2){
            unordered_map<int, int> d, distu, distv;
            bfs_distance(node[0], d);

            int u = node[0];
            for(auto [x, y]: d) if(y > d[u]) u = x;

            bfs_distance(u, distu);

            int v = u;
            for(auto [x, y]: distu) if(y > distu[v]) v = x;

            bfs_distance(v, distv);

            for(int x: node) chain[x] = max(distu[x], distv[x]) + 1;
            diam = max(diam, distu[v] + 1);
        }
    }

    if(diam) res = {1, diam};
    
    for (int v = 1; v <= n; v++){
        if(a[v] > 1){
            unordered_map<int, int> cmp;
            for(int u: adj[v]){
                if(a[u] > 1) continue;
                if(cmp.find(id[u]) == cmp.end() || cmp[id[u]] < chain[u]) cmp[id[u]] = chain[u];
            }
            if(cmp.empty()) continue;
            vector<int> val;
            for(auto [x, y]: cmp) val.push_back(y);
            pair<int, int> cand = {a[v], (1 + val[0] + (val.size() >= 2 ? val[1] : 0))};
            if(smaller(cand, res)) res = cand; 
        }
    }
    
    int x = gcd(res.first, res.second);
    cout << res.first / x << "/" << res.second / x << "\n";
}

• 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