Submission #494639

#	Time	Username	Problem	Language	Result	Execution time	Memory
494639		Ozy	Race (IOI11_race)	C++17	100 / 100	1584 ms	57636 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define LIM 1000000000000
#define MAX 200000
#define des first
#define val second

lli n,k,a,b,c,res,cnt;
lli inval[MAX+2],sub[MAX+2];
vector< pair<lli,lli> > hijos[MAX+2];
set<pair<lli,lli> >::iterator it,ot;

lli inicia(lli pos, lli padre) {

    sub[pos] = 1;
    for (auto h : hijos[pos]) {
        if (h.des == padre) continue;
        if (inval[h.des] == 1) continue;
        sub[pos] += inicia(h.des,pos);
    }

    return sub[pos];
}

lli busca(lli pos,lli padre, lli mitad) {

    for (auto h : hijos[pos]) {
        if (h.des == padre) continue;
        if (inval[h.des] == 1) continue;
        if (sub[h.des] > mitad) return busca(h.des,pos,mitad);
    }
    return pos;
}

void llena(lli pos, lli padre, lli cant, lli sum, set<pair<lli,lli> > &act) {

    if (sum > k) return;

    it = act.lower_bound({sum,0});

    if (it == act.end()) act.insert({sum,cant});
    else if ((*it).first != sum) act.insert({sum,cant});
    else if ((*it).second > cant) {
        act.erase(it);
        act.insert({sum,cant});
    }

    for (auto h : hijos[pos]) {
        if (h.des == padre) continue;
        if (inval[h.des] == 1) continue;
        llena(h.des,pos,cant+1,sum+h.val,act);
    }
}

void solve(lli pos, lli tam) {
    a = inicia(pos,-1);
    pos = busca(pos,-1,tam/2);

    set<pair<lli,lli> > op;
    for (auto h : hijos[pos]) {
        if (inval[h.des] == 1) continue;

        set<pair<lli,lli> > act;
        llena(h.des,pos,1,h.val,act);

        it = act.begin();
        while (it != act.end()) {

            a = k - (*it).first;
            b = (*it).second;
            it++;

            ot = op.lower_bound({a,0});
            if (ot == op.end()) continue;
            if ((*ot).first != a) continue;

            b += (*ot).second;
            res = min(res,b);
        }

        it = act.begin();
        while (it != act.end()) {
            a = (*it).first;
            b = (*it).second;
            it++;

            ot = op.lower_bound({a,0});
            if (ot != op.end() && (*ot).first == a){
                if ((*ot).second <= b) continue;
                op.erase(ot);
            }
            op.insert({a,b});
        }
    }

    ot = op.lower_bound({k,0});
    if (ot != op.end()) res = min(res,(*ot).second);



    inval[pos] = 1;
    vector<pair<lli,lli> > sig;
    for (auto h : hijos[pos]) {
        if (inval[h.des] == 1) continue;
        if (sub[h.des] > sub[pos]) {
            a = tam - sub[pos];
            sig.push_back({h.des, a});
        }
        else sig.push_back({h.des, sub[h.des]});
    }
    for (auto s : sig) solve(s.first,s.second);
}

int best_path(int N, int K, int H[][2], int L[])
{

    n = N;
    k = K;
    rep(i,0,n-2) {
        a = H[i][0];
        b = H[i][1];
        c = L[i];

        hijos[a].push_back({b,c});
        hijos[b].push_back({a,c});
    }

    res = LIM;
    solve(0,n);

    if (res == LIM) return -1;
    else return res;
}

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