Submission #494627

#	Time	Username	Problem	Language	Result	Execution time	Memory
494627		Ozy	Race (IOI11_race)	C++17	0 / 100	3 ms	5068 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define lli 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;
lli inval[MAX+2],sub[MAX+2];
vector< pair<lli,lli> > hijos[MAX+2];
set<pair<lli,lli> >::iterator it;

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);
    lli centro = busca(pos,-1,tam/2);

    vector<lli> op;
    op.resize(k+2,0);

    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++;

            if (op[a] == 0) continue;
            b += op[a];

            res = min(res,b);
        }

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

            if (op[a] == 0) op[a] = b;
            else op[a] = min(op[a],b);
        }
    }

    if (op[k] != 0) res = min(op[k],res);



    inval[pos] = 1;
    vector<pair<lli,lli> > sig;
    for (auto h : hijos[pos]) {
        if (inval[h.des] == 1) continue;
        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;
}

Compilation message (stderr)

race.cpp: In function 'void solve(int, int)':
race.cpp:65:9: warning: unused variable 'centro' [-Wunused-variable]
   65 |     lli centro = busca(pos,-1,tam/2);
      |         ^~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:10:13: warning: overflow in conversion from 'long int' to 'int' changes value from '1000000000000' to '-727379968' [-Woverflow]
   10 | #define LIM 1000000000000
      |             ^~~~~~~~~~~~~
race.cpp:127:11: note: in expansion of macro 'LIM'
  127 |     res = LIM;
      |           ^~~

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