Submission #488046

#	Time	Username	Problem	Language	Result	Execution time	Memory
488046		macktvz	Race (IOI11_race)	C++17	0 / 100	6 ms	8932 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(Ki,-1);
bool cen[Ni];
int sz[Ni];
int mini = Ni;
int k;
vector<int> tr;
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 && sz[i.first] > n/2 && !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), tr.push_back(ps);
    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 solve(int u, int centr) {
    dsz(u,centr);
    int cent = centroid(u,centr,sz[u]);
    cen[cent]=true;
    tr.clear();
    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(int i : tr) cnt[i]=-1; 
    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[0] = 0;
    solve(1,-1);
    return mini;
}

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