Submission #417898

#	Time	Username	Problem	Language	Result	Execution time	Memory
417898		OttoTheDino	Race (IOI11_race)	C++17	9 / 100	267 ms	47276 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

#define rep(i,s,e)                          for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                         for (int i = s; i >= e; --i)
#define pb                                  push_back
#define fi                                  first
#define se                                  second
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int mxn = 3e5;
int ans = INT_MAX, dep[mxn], hdep[mxn], sz[mxn], bot[mxn], k;
vii neibs[mxn];
map<int, int> deep[mxn];

void get_depth (int u, int prev) {
    //cout << u << endl;
    sz[u] = 1;
    for (ii vd : neibs[u]) {
        int v = vd.fi, d = vd.se;
        if (v == prev) continue;
        dep[v] = dep[u]+d;
        hdep[v] = hdep[u]+1;
        get_depth (v, u);
        sz[u] += sz[v];
    }
}

void dfs (int u, int prev) {
    //cout << u << endl;
    int heavy = -1, ma = 0;
    for (ii vd : neibs[u]) {
        int v = vd.fi;  
        if (v == prev) continue;
        dfs (v, u);
        if (sz[v] > ma) {
            ma = sz[v];
            heavy = v;
        }
    }

    if (heavy==-1) {
        bot[u] = u;
        deep[u][dep[u]] = hdep[u]; 
        return;
    }

    bot[u] = bot[heavy];

    //TODO: add u to deep

    for (ii vd : neibs[u]) {
        int v = vd.fi;
        if (v == prev || v == heavy) continue;

        for (ii deps : deep[bot[v]]) {
            int real_dep = deps.fi, high_dep = deps.se;
            int need_dep = k+2*dep[u]-real_dep;
            //cout << ans << endl;
            if (deep[bot[u]][need_dep]) ans = min(ans, high_dep+deep[bot[u]][need_dep]-2*hdep[u]);
            //cout << ans << " " << u << "\n";
        }

        for (ii deps : deep[bot[v]]) {
            int real_dep = deps.fi, high_dep = deps.se;
            if (!deep[bot[u]][real_dep] || high_dep < deep[bot[u]][real_dep]) deep[bot[u]][real_dep] = high_dep;
        }
    }

    int need_dep = k+dep[u];
    if (deep[bot[u]][need_dep]) ans = min(ans, deep[bot[u]][need_dep]-hdep[u]);
    if (!deep[bot[u]][dep[u]] || hdep[u] < deep[bot[u]][dep[u]]) deep[bot[u]][dep[u]] = hdep[u];
}

int best_path (int n, int ok, int h[][2], int l[]) {
    k = ok;
    rep (i,0,n-2) {
        int a = h[i][0], b = h[i][1], c = l[i];
        neibs[a].pb({b,c}), neibs[b].pb({a,c});
    }

    get_depth(0,-1);

    //cout << "got depth!" << endl;

    dfs (0, -1);

    return (ans==INT_MAX?-1:ans);
}

//int main() {
//    ios::sync_with_stdio(0);
//    cin.tie(0);

    //first test case

 //   int a1[3][2] = {{0,1},{1,2},{1,3}};
 //   int b1[3] = {1,2,4};

 //   cout << best_path (4, 3, a1, b1) << "\n";
 //   cout << "first done" << endl;

    //second test case
    
//    int a2[2][2] = {{0,1},{1,2}};
//    int b2[2] = {1,1};
//
//    cout << best_path (3, 3, a2, b2) << "\n";
//    cout << "second done" << endl;

    //third test case

//    int a3[10][2] = {{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}};
//    int b3[10] = {3,4,5,4,6,3,2,5,6,7};
//
//    cout << best_path (11, 12, a3, b3) << "\n";
//    cout << "thrird done" << endl;
//    
//    return 0;
//}

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