Submission #717229

#	Time	Username	Problem	Language	Result	Execution time	Memory
717229		TheSahib	Race (IOI11_race)	C++17	100 / 100	396 ms	100116 KiB

race

#include "race.h"
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = 2e5 + 5;

vector<pii> g[MAX];
ll dist[MAX];
ll height[MAX];


int k = 0;

void dfs1(int node, int p, int h, ll d){
    dist[node] = d;
    height[node] = h;

    for(pii to:g[node]){
        if(to.first == p) continue;
        dfs1(to.first, node, h + 1, d + to.second);
    }
}

int search(set<pair<ll, int>>& s, ll d){
    auto itr = s.lower_bound({d, 0});
    if(itr != s.end()){
        if((itr->first) == d){
            return itr->second;
        }
        else{
            return -1;
        }
    }
    else{
        return -1;
    }
}

ll ans = MAX;
set<pair<ll, int>> sets[MAX];

void dfs2(int node, int p){
    for(pii to:g[node]){
        if(to.first == p) continue;
        dfs2(to.first, node);

        int h = search(sets[to.first], dist[node] + k);
        if(h != -1) ans = min(ans, h - height[node]);

        if(sets[to.first].size() > sets[node].size()){
            swap(sets[to.first], sets[node]);
        }
    }
    for(pii to:g[node]){
        if(to.first == p) continue;
        for(auto& p:sets[to.first]){
            int h = search(sets[node], k - p.first + (dist[node] << 1));
            if(h != -1) ans = min(ans, h + p.second - (height[node] << 1));
        }

        for(auto& p:sets[to.first]){
            sets[node].insert(p);
        }
    }
    sets[node].insert({dist[node], height[node]});
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for (int i = 0; i < N - 1; i++)
    {
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs1(0, 0, 0, 0);
    dfs2(0, 0);
    if(ans == MAX) return -1;
    else return ans;
}

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