Submission #1270252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270252		duckpham27	Topical (NOI23_topical)	C++20	0 / 100	1 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int n, k;
vector<pair<int,ll>> adj[200005]; // cây

// =================== Subtask 1: Brute Force (n <= 20) ===================
ll distSmall[25][25];

ll subtask1() {
    // Floyd-Warshall để tính dist[u][v]
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            distSmall[i][j] = (i==j?0:INF);

    for (int u=1; u<=n; u++) {
        for (auto [v,w]: adj[u]) {
            distSmall[u][v] = min(distSmall[u][v], w);
        }
    }
    for (int m=1; m<=n; m++)
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++)
                distSmall[i][j] = min(distSmall[i][j], distSmall[i][m] + distSmall[m][j]);

    vector<int> nodes(n);
    iota(nodes.begin(), nodes.end(), 1);

    ll ans = INF;
    vector<int> mask;
    // sinh tổ hợp
    vector<int> choose(n,0);
    fill(choose.begin(), choose.begin()+k, 1);
    do {
        vector<int> S;
        for (int i=0; i<n; i++) if (choose[i]) S.push_back(i+1);
        ll val = 0;
        for (int u=1; u<=n; u++) {
            ll best = INF;
            for (int v: S) best = min(best, distSmall[u][v]);
            val = max(val, best);
        }
        ans = min(ans, val);
    } while (prev_permutation(choose.begin(), choose.end()));

    return ans;
}

// =================== Subtask 2: k = 1 (radius of tree) ===================
pair<int,ll> dfs_far(int u, int p, ll d) {
    pair<int,ll> res = {u,d};
    for (auto [v,w]: adj[u]) if (v!=p) {
        auto cur = dfs_far(v,u,d+w);
        if (cur.second > res.second) res = cur;
    }
    return res;
}

ll subtask2() {
    auto A = dfs_far(1,-1,0);
    auto B = dfs_far(A.first,-1,0);
    ll diameter = B.second;
    return (diameter+1)/2;
}

// =================== Subtask 3: Path tree (line) ===================
ll subtask3() {
    // Tính prefix khoảng cách
    vector<ll> prefix(n+1,0);
    for (int i=2; i<=n; i++) {
        for (auto [v,w]: adj[i]) if (v==i-1) {
            prefix[i] = prefix[i-1] + w;
        }
    }
    // binary search đáp án
    ll lo=0, hi=prefix[n], ans=hi;
    auto check = [&](ll X)->bool {
        int used=0;
        int pos=1;
        while (pos<=n) {
            used++;
            ll reach = prefix[pos] + 2*X; // cover trong khoảng cách X
            int nxt=pos;
            while (nxt<=n && prefix[nxt]-prefix[pos]<=2*X) nxt++;
            pos=nxt;
            if (used>k) return false;
        }
        return true;
    };
    while (lo<=hi) {
        ll mid=(lo+hi)/2;
        if (check(mid)) { ans=mid; hi=mid-1; }
        else lo=mid+1;
    }
    return ans;
}

// =================== Subtask 4: General tree (binary search + greedy) ===================
int usedCenters;
ll limitX;

bool dfs_cover(int u, int p) {
    ll maxNeed = -INF;
    for (auto [v,w]: adj[u]) if (v!=p) {
        if (dfs_cover(v,u)) return true;
    }
    // giả sử ta check từ lá lên (thực tế cần coding chi tiết hơn),
    // ở đây mình viết dạng khung cho sub4.
    return false;
}

bool check_general(ll X) {
    // TODO: viết DFS greedy chuẩn
    // Đếm số trạm cần <= k
    return true; // placeholder
}

ll subtask4() {
    ll lo=0, hi=1e15, ans=hi;
    while (lo<=hi) {
        ll mid=(lo+hi)/2;
        if (check_general(mid)) { ans=mid; hi=mid-1; }
        else lo=mid+1;
    }
    return ans;
}

// =================== MAIN ===================
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i=1; i<n; i++) {
        int a,b; ll c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    ll ans=0;
    if (n<=20) ans = subtask1();
    else if (k==1) ans = subtask2();
    else {
        bool isPath=true;
        for (int i=1; i<=n; i++) {
            if (adj[i].size()>2) { isPath=false; break; }
        }
        if (isPath) ans = subtask3();
        else ans = subtask4();
    }

    cout << ans << "\n";
    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 28
• Subtask 3: 0 / 21
• Subtask 4: 0 / 39