Submission #310870

#	Time	Username	Problem	Language	Result	Execution time	Memory
310870		lohacho	Race (IOI11_race)	C++14	21 / 100	3066 ms	40180 KiB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)2e5 + 4;
int N, k;
vector<pair<int, int>> way[NS];
int chk[NS], sz[NS], rt;
int dis[(int)1e6 + 4];
int ans;
vector<int> did;
vector<pair<int, int>> put;

void getroot(int now, int pr, int alls){
    sz[now] = 1;
    int f = 1;
    for(auto&nxt:way[now]){
        if(nxt.first == pr || chk[nxt.first]){
            continue;
        }
        getroot(nxt.first, now, alls);
        sz[now] += sz[nxt.first];
        if(sz[nxt.first] > alls / 2){
            f = 0;
        }
    }
    if(f){
        rt = now;
    }
}

void getdis(int now, int ndis, int pr, int ndep){
    int need = k - ndis;
    if(need >= 0){
        ans = min(ans, ndep + dis[need]);
    }
    for(auto&nxt:way[now]){
        if(nxt.first == pr || chk[nxt.first]){
            continue;
        }
        getdis(nxt.first, ndis + nxt.second, now, ndep + 1);
    }
    if(ndis < (int)1e6 + 4){
        if(dis[ndis] > ndep){
            put.push_back({ndis, ndep});
            did.push_back(ndis);
        }
    }
}

void sol(int now, int alls){
    dis[0] = 0;
    chk[now] = 1;
    did.clear();
    for(int i = 0; i < (int)way[now].size(); ++i){
        if(chk[way[now][i].first]){
            continue;
        }
        getdis(way[now][i].first, way[now][i].second, now, 1);
        while((int)put.size()){
            dis[put.back().first] = min(dis[put.back().first], put.back().second);
            put.pop_back();
        }
    }
    while((int)did.size()){
        dis[did.back()] = MOD;
        did.pop_back();
    }
    for(auto&nxt:way[now]){
        if(chk[nxt.first]){
            continue;
        }
        int nsz = (sz[nxt.first] > sz[now] ? alls - sz[now]:sz[nxt.first]);
        getroot(nxt.first, now, nsz);
        sol(rt, nsz);
    }
}


int best_path(int n, int K, int H[][2], int L[])
{
    for(int i = 0; i < (int)1e6 + 4; ++i){
        dis[i] = MOD;
    }
    ans = MOD;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    N = n, k = K;
    for(int i = 0; i < N - 1; ++i){
        int a, b, c;
        a = H[i][0], b = H[i][1], c = L[i];
        way[a].push_back({b, c}), way[b].push_back({a, c});
    }
    getroot(1, -1, N);
    sol(rt, N);
    if(ans == MOD){
        return -1;
    }
    else{
        return ans;
    }
}

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