Submission #1280031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280031		dex111222333444555	Race (IOI11_race)	C++17	100 / 100	427 ms	32492 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define ii pair<int, int>
#define fi first
#define se second
#define sz(v) ((int)(v).size())
#define all(v) begin((v)), end(v)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define dbg(x) "[" #x " = " << x << "]"
using namespace std;
const int MAXN = 2e5 + 5, infINT = 1e9 + 23737, MAXV = 1e6 + 5;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int numNode, numReq, best[MAXV], sz[MAXN], res = MAXN + 1;
bool del[MAXN];
vector<ii> adj[MAXN];
vector<int> can;

void updateAns(int u, bool type, int sumDist, int step = 1, int par = 0){
    if (sumDist > numReq) return;
    can.push_back(sumDist);
    if (type){
        minimize(res, best[numReq - sumDist] + step);
    }else{
        minimize(best[sumDist], step);
    }
    for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
        int v = x.fi, w = x.se;
        updateAns(v, type, sumDist + w, step + 1, u);
    }
}

int getSize(int u, int par = 0){
    sz[u] = 1;
    for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
        int v = x.fi, w = x.se;
        sz[u] += getSize(v, u);
    }
    return sz[u];
}

int getCentroid(int sizeU, int u, int par = 0){
    for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
        int v = x.fi, w = x.se;
        if (sz[v] > (sizeU >> 1)) return getCentroid(sizeU, v, u);
    }
    return u;
}

void decomp(int u = 1){
    int centroid = getCentroid(getSize(u), u);
    del[centroid] = 1;

    can.clear();

    for(ii x: adj[centroid]) if (!del[x.fi]) {
        int v = x.fi, w = x.se;
        updateAns(v, true, w);
        updateAns(v, false, w);
    }

    for(int sumDist: can) best[sumDist] = infINT;

    for(ii x: adj[centroid]) if (!del[x.fi]){
        int v = x.fi, w = x.se;
        decomp(v);
    }
}

int best_path(int N, int K, int edge[][2], int len[])
{
    numNode = N; numReq = K;
    for(int i = 0; i < numNode - 1; i++){
        int u = edge[i][0] + 1, v = edge[i][1] + 1;
        adj[u].push_back({v, len[i]});
        adj[v].push_back({u, len[i]});
    }
    memset(best, 0x3f, sizeof best);
    best[0] = 0;
    decomp();
    return (res <= MAXN ? res: -1);
}

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