Submission #1278095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278095		Robert_junior	Race (IOI11_race)	C++20	0 / 100	16 ms	25916 KiB

race

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7, mod = 1e9 + 7;
int tin[N], tout[N], d[N], d1[N], sz[N], bc[N], b[N], mn[N], timer;
vector<pair<int, int>>g[N];
int n, k;
void dfs(int v, int p){
    sz[v] = 1;
    tin[v] = ++timer;
    b[tin[v]] = v; 
    for(auto [to, w] : g[v]){
        if(to == p) continue;
        d[to] = d[v] + 1;
        d1[to] = d1[v] + w;
        dfs(to, v);
        sz[v] += sz[to];
        if(sz[to] > sz[bc[v]]) bc[v] = to;
    }
    tout[v] = timer;
}
int res = INT_MAX;
vector<int>cl;
void dfs1(int v, int p, bool keep){
    for(auto [to, w] : g[v]){
        if(to == p || to == bc[v]) continue;
        dfs1(to, v, 0);
    }
    if(bc[v]) dfs1(bc[v],v, 1); 
    for(auto [to, w] : g[v]){
        if(to == p || to == bc[v]) continue;
        for(int i = tin[to]; i <= tout[to]; i++){
            int u = b[i];
            int w = k + d[v] * 2 - d[u];
            res = min(res, d[u] + mn[w] - 2 * d[v]);
        }
        for(int i = tin[to]; i <= tout[to]; i++){
            int u = b[i];
            cl.push_back(d1[u]);
            mn[d1[u]] = min(mn[d1[u]], d[u]);
        }
    }
    mn[d1[v]] = min(mn[d1[v]], d[v]);
    cl.push_back(d1[v]);
    if(!keep){
        for(auto it : cl) mn[it] = INT_MAX;
        cl.clear();
    }
}
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 a = H[i][0], b = H[i][1], c = L[i];
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    for(int i = 1; i <= 1000000; i++){
        mn[i] = INT_MAX;
    }
    dfs(0, 0);
    dfs1(0, 0, 0);
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
   62 | }
      | ^

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