Submission #915494

#	Time	Username	Problem	Language	Result	Execution time	Memory
915494		Julto	Race (IOI11_race)	C++14	9 / 100	1057 ms	74960 KiB

race

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int mxN = 2e5 + 5, inf = 1e9;

int sz[mxN], cenPar[mxN], dep[mxN], par[mxN][18], sum[mxN], cnt = 0;
vector<int> first(mxN, -1);
vector<array<int, 2>> adj[mxN], euler;
vector<array<int, 3>> dists[mxN];
bool done[mxN];

void dfs(int u, int p){
    if(first[u] == -1){
        first[u] = cnt++;
    }
    euler.push_back({dep[u], u});
    for(auto i : adj[u]){
        if(i[0] == p) continue;
        dep[i[0]] = dep[u] + 1;
        sum[i[0]] = sum[u] + i[1];
        dfs(i[0], u);
        euler.push_back({dep[u], u});
    }
}

array<int, 2> table[2 * mxN][20];
int lg[2 * mxN];

void initTable(){
    for(int i = 2; i < 2 * mxN; i++){
        lg[i] = lg[i / 2] + 1;
    }
    int sz = euler.size();
    for(int i = 0; i < sz; i++){
        table[i][0] = euler[i];
    }

    for(int j = 1; j < 20; j++) {
        for(int i = 0; i + (1 << j) <= sz; i++) {
            table[i][j] = min(table[i][j-1], table[i + (1 << (j-1))][j-1]);
        }
    }
}

int lca(int a, int b){
    a = first[a];
    b = first[b];
    if(a > b) swap(a, b);
    int j = lg[b + 1 - a];
    return min(table[a][j], table[b + 1 - (1<<j)][j])[1];
}

int calcDist(int a, int b){
    return sum[a] + sum[b] - 2 * sum[lca(a, b)];
}

int calcSz(int u, int p){
    sz[u] = 1;
    for(auto i : adj[u]){
        if(i[0] == p || done[i[0]]) continue;
        sz[u] += calcSz(i[0], u);
    }
    return sz[u];
}

int get(int u, int p, int x){
    for(auto i : adj[u]){
        if(i[0] == p || done[i[0]]) continue;
        if(sz[i[0]] * 2 > x){
            return get(i[0], u, x);
        }
    }
    return u;
}

int build(int u){
    int centroid = get(u, u, calcSz(u, u));
    done[centroid] = 1;
    dists[centroid].push_back({0, centroid, centroid});
    for(auto i : adj[centroid]){
        if(!done[i[0]]){
            int x = build(i[0]);
            cenPar[x] = centroid;
            for(auto j : dists[x]){
                dists[centroid].push_back({calcDist(centroid, j[2]), x, j[2]});
            }
        }
    }
    sort(dists[centroid].begin(), dists[centroid].end());
    return centroid;
}

int qry(int v, int k){
    int cur = v, subtree = v;
    int ans = inf;
    while(cur != -1){
        int goal = k - calcDist(v, cur);
        array<int, 3> find = {goal, -inf, -inf};
        int lb = lower_bound(dists[cur].begin(), dists[cur].end(), find) - dists[cur].begin();
        for(int j = lb; j < dists[cur].size() && dists[cur][j][0] == goal; j++){
            if(dists[cur][j][1] == subtree) continue;
            int x = dep[v] + dep[cur] - 2 * dep[lca(cur, v)];
            int y = dep[dists[cur][j][2]] + dep[cur] - 2 * dep[lca(dists[cur][j][2], cur)];
            ans = min(ans, x + y);
            //cout << v << " " << dists[cur][j][2] << ' ' << x + y << '\n';
        }
        subtree = cur;
        cur = cenPar[cur];

    }
    return ans;
}

int best_path(int n, int k, int h[][2], int l[]){
    for(int i = 0; i < n - 1; i++){
        adj[h[i][0]].push_back({h[i][1], l[i]});
        adj[h[i][1]].push_back({h[i][0], l[i]});
    }
    dfs(0, 0);
    initTable();
    for(int i = 0; i < n; i++){
        cenPar[i] = -1;
    }
    build(0);
    /*for(int i = 0; i < n; i++){
        cout << cenPar[i] << " ";
    }
    cout << '\n';
    for(int i = 0; i < n; i++){
        cout << i << '\n';
        for(auto j : dists[i]){
            cout << j[0] << " " << j[1] << " " << j[2] << "\n";
        }
        cout << '\n';
    }*/
    int ans = inf;
    for(int i = 0; i < n; i++){
        //cout << qry(i, k) << " ";
        ans = min(ans, qry(i, k));
    }

    return (ans == inf ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'int qry(int, int)':
race.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j = lb; j < dists[cur].size() && dists[cur][j][0] == goal; j++){
      |                         ~~^~~~~~~~~~~~~~~~~~~

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