Submission #900118

#	Time	Username	Problem	Language	Result	Execution time	Memory
900118		Macker	Race (IOI11_race)	C++17	100 / 100	1100 ms	55056 KiB

race

#include "race.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")

vector<vector<pair<int, int>>> adj;
vector<int> centroid;
vector<int> sz;
int k;

int szDfs(int a, int p){
    sz[a] = 1;
    for (auto &[b, _] : adj[a]) {
        if(b == p || centroid[b]) continue;
        sz[a] += szDfs(b, a);
    }
    return sz[a];
}

int getCentroid(int a, int p, int curSz){
    for (auto &[b, _] : adj[a]) {
        if(b == p || centroid[b]) continue;
        if(sz[b] * 2 > curSz) return getCentroid(b, a, curSz);
    }
    return a;
}

void dDfs(int a, int p, int d, int dc, vector<pair<int, int>> &dst){
    dst.push_back({dc, d});
    for (auto &[b, c] : adj[a]) {
        if(b == p || centroid[b]) continue;
        dDfs(b, a, d + 1, dc + c, dst);
    }
}

int getBest(int a){
    multiset<pair<int, int>> cur;
    cur.insert({0, 0});
    vector<vector<pair<int, int>>> ch;
    int res = INT_MAX;

    int ctd = getCentroid(a, a, szDfs(a, a));
    centroid[ctd] = true;

    for (auto [b, c] : adj[ctd]) {
        if(centroid[b]) continue;
        ch.push_back({});
        dDfs(b, b, 1, c, ch.back());
    }

    for (auto &&i : ch) for (auto &&j : i){
        cur.insert(j);
    }

    for (auto &&i : ch) {
        for (auto &&j : i) cur.erase(cur.find(j));
        for (auto &&j : i) {
            if(cur.lower_bound({k - j.first, 0}) == cur.end()) continue;
            pair<int, int> x = *cur.lower_bound({k - j.first, 0});
            if(x.first == k - j.first){
                res = min(res, x.second + j.second);
            }
        }
        for (auto &&j : i) cur.insert(j);
    }

    for (auto &[b, _] : adj[ctd]) {
        if(centroid[b]) continue;
        res = min(res, getBest(b));
    }
    
    return res;
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    adj.assign(N, {});
    sz.assign(N, 0);
    centroid.assign(N, false);
    for (int i = 0; i < N - 1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    int ret = getBest(0);
    if(ret == INT_MAX) return -1;
    return ret;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57