Submission #636701

#	Time	Username	Problem	Language	Result	Execution time	Memory
636701		rainliofficial	Race (IOI11_race)	C++17	0 / 100	11 ms	14420 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define sz(x) (int)x.size()

const int MAXN = 2e5+5, INF = 1e9;
int n, k, ans = INF, h[MAXN][2], l[MAXN];
vector<pii> arr[MAXN];
set<pii> vals[MAXN];
pii offset[MAXN];

void solve(int at, int parent, int cost){
    // Find the largest subtree
    int big = at, bigCost = 0;
    for (pii i : arr[at]){
        if (i.first != parent){
            solve(i.first, at, i.second);
            if (vals[i.first].size() > vals[big].size()){
                big = i.first;
                bigCost = i.second;
            }
        }
    }
    
    if (at != big){
        swap(vals[at], vals[big]); // Copy the largest subtree
        offset[at] = offset[big];
        offset[at].first += bigCost;
        offset[at].second++;
    }
    
    // Manually add the remaining elements
    for (pii i : arr[at]){
        if (i.first != parent && i.first != big){ // Since vals[big] is empty now (we called swap() on it), we don't have to worry about it anymore
            for (pii x : vals[i.first]){
                int costNeeded = k - (x.first + offset[i.first].first + i.second) - offset[at].first;
                int adjDist = x.second + offset[i.first].second - offset[at].second;
                if (costNeeded == 0){
                    ckmin(ans, adjDist + offset[at].second);
                    continue;
                }
                auto it = vals[big].lower_bound({costNeeded, -INF});
                if (it != vals[big].end() && (*it).first == costNeeded){
                    ckmin(ans, (*it).second + offset[at].second + adjDist);
                }
            }
            for (pii x : vals[i.first]){
                int adjCost = (x.first + offset[i.first].first + i.second) - offset[at].first;
                int adjDist = x.second + offset[i.first].second - offset[at].second;
                vals[at].insert({adjCost, adjDist});
            }
        }
    }
    auto it = vals[at].lower_bound({k - offset[at].first, -INF});
    if (it != vals[big].end() && (*it).first == k - offset[at].first){
        ckmin(ans, (*it).second + offset[at].second);
    }
    vals[at].insert({-offset[at].first, -offset[at].second});
}

int best_path(int N, int K, int h[][2], int l[]){
    n = N, k = K;
    for (int i=0; i<n-1; i++){
        int a = h[i][0], b = h[i][1];
        arr[a].push_back({b, l[i]});
        arr[b].push_back({a, l[i]});
    }
    solve(0, -1, 0);
    return ans != INF ? ans : -1;
}



/**
 * Debugging checklist:
 * - Reset everything after each TC
 * - Integer overflow, index overflow
 * - Special cases?
 */

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