Submission #488058

#	Time	Username	Problem	Language	Result	Execution time	Memory
488058		macktvz	Race (IOI11_race)	C++17	0 / 100	4 ms	4960 KiB

race

#include <bits/stdc++.h>

using namespace std;
const int Ni = 200001;
const int Ki = 1e6+1;
vector<pair<int,int>> adj[Ni];
vector<int> cnt;
bool cen[Ni];
int sz[Ni];
int mini = Ni;
int k;

void dsz(int u, int p) {
    sz[u] = 1;
    for(pair<int,int> i : adj[u]) {
        if (i.first != p && !cen[i.first]) {
            dsz(i.first,u);
            sz[u] += sz[i.first];
        }
    }
}
int centroid(int u,int p,int n) {
    for(pair<int,int> i : adj[u]) {
        if (i.first != p && 2*sz[i.first] > n && !cen[i.first]) return centroid(i.first,u,n);
    }
    return u;
}
void find(int u, int p, int currl, int ps, bool add) {
    if (ps > k) return;
    if (add) cnt[ps] = cnt[ps]==-1 ? currl : min(cnt[ps],currl);
    else if (cnt[k-ps] != -1) mini = min(mini,currl+cnt[k-ps]);
    for(pair<int,int> i : adj[u]) {
        if (i.first != p && !cen[i.first]) {
            find(i.first,u,currl+1,ps+i.second,add);
        }
    }
} 
void del(int u, int p, int ps) {
    if (ps > k) return;
    cnt[ps] = -1;
    for(pair<int,int> i : adj[u]){
        if (i.first != p && !cen[i.first]) del(i.first,u,ps+i.second);
    }
}
void solve(int u, int centr) {
    dsz(u,centr);
    int cent = centroid(u,centr,sz[u]);
    cen[cent]=true;
    
    for(pair<int,int> i : adj[cent]) {
        if (!cen[i.first]) {
            find(i.first,cent,1,i.second,0);
            find(i.first,cent,1,i.second,1);
        }
    }
    for(pair<int,int> i : adj[cent]) {
        if (!cen[i.first]) {
            del(i.first,cent,i.second);
        }
    }
    for(pair<int,int> i : adj[cent]) {
        if (!cen[i.first]) solve(i.first,cent);
    }
}
int best_path(int N,int K,int H[][2],int L[]) {
    for(int i = 0; i < N; i++) {
        adj[H[i][0]].push_back({H[i][1],L[i]});
        adj[H[i][1]].push_back({H[i][0],L[i]});
    }
    k=K;
    cnt.resize(K+1);
    fill(begin(cnt),end(cnt),-1);
    cnt[0] = 0;
    solve(0,-1);
    return mini == Ni ? -1 : mini;
}

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