Submission #339257

#	Time	Username	Problem	Language	Result	Execution time	Memory
339257		rocks03	Race (IOI11_race)	C++14	100 / 100	641 ms	46796 KiB

race

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 5e5+100;
int K, sz[MAXN];
vector<pii> g[MAXN];
bool vis[MAXN];

void centroid(int v, int p, int csz, int& ans){
    sz[v] = 1; bool is = true;
    for(auto [u, w] : g[v]){
        if(u == p || vis[u]) continue;
        centroid(u, v, csz, ans);
        sz[v] += sz[u];
        if(sz[u] * 2 > csz){
            is = false;
        }
    }
    if((csz - sz[v]) * 2 <= csz && is){
        ans = v;
    }
}

const int MAXK = 1e6+100;
int arr[MAXK];
void dfs(int v, int p, int d, int len, vector<pii>& vch){
    if(d > K) return;
    vch.pb({d, len});
    for(auto [u, w] : g[v]){
        if(u == p || vis[u])
            continue;
        dfs(u, v, d + w, len + 1, vch);
    }
}

int solve(int v, int p, int csz){
    centroid(v, p, csz, v);
    int ans = INT_MAX;
    vector<int> vrt;
    for(int i = 0; i < SZ(g[v]); i++){
        int u = g[v][i].ff, w = g[v][i].ss;
        if(u == p || vis[u]) continue;
        vector<pii> vch;
        dfs(u, v, w, 1, vch);
      	arr[0] = 0;
        for(auto [d, len] : vch){
            if(arr[K - d] != INT_MAX){
                ans = min(ans, arr[K - d] + len);
            }
            vrt.pb(d);
        }
        for(auto [d, len] : vch){
            arr[d] = min(arr[d], len);
        }
    }
    for(auto d : vrt){
        arr[d] = INT_MAX;
    }
    vis[v] = true;
    for(auto [u, w] : g[v]){
        if(u == p || vis[u])
            continue;
        ans = min(ans, solve(u, v, sz[u]));
    }
    return ans;
}

int best_path(int N, int K, int H[][2], int L[]){
    :: K = K;
    for(int i = 0; i < N - 1; i++){
        int u = H[i][0], v = H[i][1];
        g[u].pb({v, L[i]});
        g[v].pb({u, L[i]});
    }
    fill(arr, arr + MAXK, INT_MAX);
    int ans = solve(0, -1, N);
    if(ans == INT_MAX){
        ans = -1;
    }
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void centroid(int, int, int, int&)':
race.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [u, w] : g[v]){
      |              ^
race.cpp: In function 'void dfs(int, int, int, int, std::vector<std::pair<int, int> >&)':
race.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto [u, w] : g[v]){
      |              ^
race.cpp: In function 'int solve(int, int, int)':
race.cpp:58:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         for(auto [d, len] : vch){
      |                  ^
race.cpp:64:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         for(auto [d, len] : vch){
      |                  ^
race.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for(auto [u, w] : g[v]){
      |              ^

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