Submission #787667

#	Time	Username	Problem	Language	Result	Execution time	Memory
787667		Ronin13	Race (IOI11_race)	C++17	100 / 100	364 ms	54940 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int kmax = 1000001;
const int nmax = 1000001;


vector <vector <pii> > g(nmax);
int d[nmax];
vector <bool> marked(nmax);
int k;
int n;

int ans = 1e9;

void DFS(int v, int e, int depth, int D){
    ans = min(ans, d[k - depth] + D);
    for(auto x: g[v]){
        int to = x.f;
        int len = x.s;
        if(to == e || marked[to]) continue;
        if(depth + len > k) continue;
        DFS(to, v, depth + len, D + 1);
    }
}

void upd(int v, int e, int depth, int D){
    d[depth] = min(d[depth], D);
    for(auto x : g[v]){
        int to = x.f;
        int len = x.s;
        if(to == e || marked[to]) continue;
        if(depth + len > k) continue;
        upd(to, v, depth + len, D + 1);
    }
}

void clear_dfs(int v, int e, int depth){
    d[depth] = 1e9;
    for(auto x : g[v]){
        int to = x.f;
        int len = x.s;
        if(to == e || marked[to]) continue;
        if(depth + len > k) continue;
        clear_dfs(to, v, depth + len);
    }
}

int sz[nmax];

void dfs(int v, int e){
  sz[v] = 1;
    for(auto x : g[v]){
      int to = x.f;
      if(marked[to] || to == e) continue;
      dfs(to, v);
      sz[v] += sz[to];
    }
}

int find_cent(int v, int e, int n){
    for(auto xx : g[v]){
      int to = xx.f;
      if(marked[to] || to == e) continue;
      if(sz[to] * 2 >= n) return find_cent(to, v, n);
    }
    return v;
}

void decompose(int v){
    dfs(v, v);
    int x = find_cent(v, v, sz[v]);
    //cout << 1;
    d[0] = 0;
    for(auto xx : g[x]){
        int to = xx.f, len = xx.s;
        if(marked[to]) continue;
        if(len <= k){
            DFS(to, x, len, 1);
            upd(to, x, len, 1);
        }
    }
    clear_dfs(x, x, 0);
    marked[x] = true;
    for(auto xx : g[x]){
        int to = xx.f;
        if(marked[to]) continue;
        decompose(to);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    int n = N;
    for(int i = 0; i < N - 1; i++){
        int u = H[i][0], v = H[i][1], w = L[i];
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    for(int i = 0; i <= k; i++){
      d[i] = 1e9;
    }
    decompose(0);
    if(ans == 1e9) ans = -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:104:9: warning: unused variable 'n' [-Wunused-variable]
  104 |     int n = N;
      |         ^

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