Submission #747989

#	Time	Username	Problem	Language	Result	Execution time	Memory
747989		vjudge1	Race (IOI11_race)	C++14	0 / 100	1 ms	212 KiB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

struct edge{
    int to, w;
};

int n, k;
vector<vector<edge>> v;
int ans = 1e9;
vector<bool> voltcentroid;
vector<int> siz;
map<int, int> m;

int szamoz(int x, int p = -1){
    siz[x] = 1;
    for(edge&i : v[x]){
        if(!voltcentroid[i.to] && i.to != p){
            siz[x] += szamoz(i.to, x);
        }
    }
    return siz[x];
}

int keres(int x, int meret, int p = -1){
    for(edge&i : v[x]){
        if(!voltcentroid[i.to] && i.to != p && siz[i.to] > meret/2){
            return keres(i.to, meret, x);
        }
    }
    return x;
}

void szamol(int x, int w, int d, int p, bool update){
    int cel = k-w;
    if (update) {
        if (m.count(w)) {
            m[w] = min(m[w], d);
        } else {
            m[w] = d;
        }
    } else {
        if(m.count(cel)){
            ans = min(ans, m[cel] + d + 1);
        }
    }
    for(edge&i : v[x]){
        if(!voltcentroid[i.to] && i.to != p){
            szamol(i.to, min(1000000+1, w + i.w), d+1, x, update);
        }
    }
}

void solve(int x = 0){
    int meret = szamoz(x);
    int centroid = keres(x, meret);

    m.clear();
    m[0] = 0;
    for(edge&i : v[centroid]){
        if(!voltcentroid[i.to]){
            szamol(i.to, i.w, 1, centroid, false);
            szamol(i.to, i.w, 1, centroid, true);
        }
    }

    voltcentroid[centroid] = true;
    for(edge&i : v[centroid]){
        if(!voltcentroid[i.to]){
            solve(i.to);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N;
    k = K;
    v.assign(n, {});
    for(int i = 0; i < n-1; i++){
        v[H[i][0]].push_back({H[i][1], L[i]});
        v[H[i][1]].push_back({H[i][0], L[i]});
    }
    voltcentroid.assign(n, 0);
    siz.assign(n, 0);
    solve();
    return ans == 1e9 ? -1 : ans;
}

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