Submission #386070

#	Time	Username	Problem	Language	Result	Execution time	Memory
386070		cpp219	Race (IOI11_race)	C++14	0 / 100	2 ms	364 KiB

race

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e3 + 6;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
vector<LL> g[N];
ll n,k,w[N],H[N][2],child[N],len[N],d[N],ans = inf,L[N];
bool Is_cent[N];
multiset<LL> All;

ll Find_cent(ll u,ll p,ll total){
    for (auto i : g[u]){
        ll v = i.fs,now = i.sc;
        if (!Is_cent[v]&&v != p&&child[v]*2 >= total) return Find_cent(v,u,total);
    }
    Is_cent[u] = 1; return u;
}

void reDFS(ll u,ll p){
    child[u] = 1;
    for (auto i : g[u]){
        ll v = i.fs,now = i.sc;
        if (!Is_cent[v] && v != p){
            len[v] = len[u] + now;  d[v] = d[u] + 1;
            reDFS(v,u); child[u] += child[v];
        }
    }
}

void Add(ll u,ll p){
    All.insert({len[u],d[u]});
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v] && v != p) Add(v,u);
    }
}

void Delete(ll u,ll p){
    auto it = All.find({len[u],d[u]});
    All.erase(it);
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v] && v != p) Delete(v,u);
    }
}

void update(ll u,ll p){
    if (len[u] <= k){
        LL it = *All.find({k - len[u],0}); //cout<<it.fs<<" "<<k <<" "<< len[u]; exit(0);
        if (it.fs == k - len[u]) ans = min(ans,it.sc + d[u]);
    }
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v] && v != p) update(v,u);
    }
}

void DFS(ll u){
    reDFS(u,0); All.clear();
    ll centroid = Find_cent(u,0,child[u]); len[centroid] = 0;
    reDFS(centroid,0); u = centroid;
    //cout<<len[2]; exit(0);
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v]) Add(v,u);
    }
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v]){
            Delete(v,u); update(v,u); Add(v,u);
        }
    }
    for (auto i : g[u]){
        ll v = i.fs;
        if (!Is_cent[v]) DFS(v);
    }
}

ll best_path(ll num,ll K,ll H[][2],ll L[]){
    n = num; k = K;
    for (ll i = 0;i < n - 1;i++){
        ll x = H[i][0],y = H[i][1]; x++; y++;
        g[x].push_back({y,L[i]}); g[y].push_back({x,L[i]});
    }
    DFS(1);
    if (ans != inf) return ans;
    return -1;
}
/*
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>k;
    for (ll i = 0;i < n - 1;i++) cin>>H[i][0]>>H[i][1];
    for (ll i = 0;i < n - 1;i++) cin>>L[i];
    cout<<best_path(n,k,H,L);
}
*/

Compilation message (stderr)

race.cpp: In function 'int Find_cent(int, int, int)':
race.cpp:18:21: warning: unused variable 'now' [-Wunused-variable]
   18 |         ll v = i.fs,now = i.sc;
      |                     ^~~

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