Submission #1056095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056095		tuandq	Race (IOI11_race)	C++17	100 / 100	312 ms	62396 KiB

race

#include <bits/stdc++.h>
using namespace std ;

template<class X, class Y>
bool minimize(X &x, const Y &y) {
    if(x > y) return x = y, true ;
    return false ;
}

const int inf = 1e9 ;
const int lim = 1e6 + 5 ;

struct E {
    int u, v, w ;
    E() {}
    E(int a, int b, int c): u(a), v(b), w(c) {}
};

int g[lim], child[lim], n, k, res = inf ;
vector<int> adj[lim] ;
bitset<lim> del ;
E e[lim] ;

int other(int i, int u) {
    return e[i].u ^ e[i].v ^ u ;
}

void dfs(int u, int par) {
    child[u] = 1 ;
    for(int i : adj[u]) {
        int v = other(i, u) ;
        if(!del[v] && v != par) {
            dfs(v, u) ;
            child[u] += child[v] ;
        }
    }
}

int find_centroid(int u, int par, int cur) {
    for(int i : adj[u]) {
        int v = other(i, u) ;
        if(!del[v] && v != par && child[v] > (cur >> 1)) {
            return find_centroid(v, u, cur) ;
        }
    }
    return u ;
}

void dfs_calc(int u, int par, int h, int len) {
    if(len > k) return ;
    minimize(res, h + g[k - len]) ;
    for(int i : adj[u]) {
        int v = other(i, u) ;
        if(!del[v] && v != par) {
            dfs_calc(v, u, h + 1, len + e[i].w) ;
        }
    }
}

void dfs_up(int u, int par, int h, int len, vector<int> &tmp) {
    if(len > k) return ;
    tmp.push_back(len) ;
    minimize(g[len], h) ;
    for(int i : adj[u]) {
        int v = other(i, u) ;
        if(!del[v] && v != par) {
            dfs_up(v, u, h + 1, len + e[i].w, tmp) ;
        }
    }
}

void decomp(int root) {
    // cerr << root << ' ' ;
    dfs(root, 0) ;
    root = find_centroid(root, 0, child[root]) ;

    vector<int> tmp ;
    for(int i : adj[root]) {
        int v = other(i, root) ;
        if(!del[v]) {
            dfs_calc(v, root, 1, e[i].w) ;
            dfs_up(v, root, 1, e[i].w, tmp) ;
        }
    }

    del.set(root) ;
    for(int k : tmp) {
        g[k] = inf ;
    }
    for(int i : adj[root]) {
        int v = other(i, root) ;
        if(!del[v]) {
            decomp(v) ;
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N ; k = K ;
    for(int i = 0; i < n - 1; i ++) {
        int u = H[i][0] + 1, v = H[i][1] + 1 ;
        e[i] = E(u, v, L[i]) ;
        adj[u].push_back(i) ;
        adj[v].push_back(i) ;
    }
    for(int i = 1; i <= lim; i ++) {
        g[i] = inf ;
    }
    decomp(1) ;
    return res == inf ? -1 : res ;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:107:14: warning: iteration 1000004 invokes undefined behavior [-Waggressive-loop-optimizations]
  107 |         g[i] = inf ;
      |         ~~~~~^~~~~
race.cpp:106:22: note: within this loop
  106 |     for(int i = 1; i <= lim; i ++) {
      |                    ~~^~~~~~

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