Submission #1000841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000841		Tsog	Race (IOI11_race)	C++14	100 / 100	289 ms	34388 KiB

race

#include "race.h"
#include "bits/stdc++.h"
using namespace std;
 
const int mxN = 2e5L + 10;
const int mxK = 1e6L + 10;
int n, k;
vector<pair<int, int>> adj[mxN];
int ans = mxN;
int sz[mxN];
bool proc[mxN] = {};
int dp[mxK];
 
int get_sz(int x, int p) {
    sz[x] = 1;
    for(auto [y, w] : adj[x]) {
        if(proc[y] || y == p) continue;
        sz[x] += get_sz(y, x);
    }
    return sz[x];
}
 
int get_cen(int x, int p, int tot) {
    for(auto [y, w] : adj[x]) {
        if(proc[y] || y == p || sz[y] * 2 <= tot) continue;
        return get_cen(y, x, tot);
    }
    return x;
}
 
void dfs(int x, int p, int dep, int dis, int flag) {
    if(dis > k) return;
    if(flag == 0) {
        if(dp[k - dis] != mxN) ans = min(ans, dep + dp[k - dis]);
    }
    else if(flag == 1) {
        dp[dis] = min(dp[dis], dep);
    }
    else if(flag == 2) {
        dp[dis] = mxN;
    }
 
    for(auto [y, w] : adj[x]) {
        if(proc[y] || y == p) continue;
        dfs(y, x, dep + 1, dis + w, flag);
    }
}
 
void solve(int x = 1, int p = -1) {
    int c = get_cen(x, p, get_sz(x, p));
    dp[0] = 0;
    for(auto [d, w] : adj[c]) {
        if(proc[d]) continue;
        dfs(d, c, 1, w, 0);
        dfs(d, c, 1, w, 1);
    }
    for(auto [d, w] : adj[c]) {
        if(proc[d]) continue;
        dfs(d, c, 1, w, 2);
    }
    dp[0] = mxN;
    proc[c] = 1;
    for(auto [d, w] : adj[c]) {
        if(proc[d]) continue;
        solve(d, c);
    }
}
 
int best_path(int N, int K, int H[][2], int L[])
{
    for(int i = 0; i < mxK; ++i) dp[i] = mxN;
    n = N; k = K;
    for(int i = 0; i < n - 1; ++i) {
        adj[H[i][0] + 1].emplace_back(H[i][1] + 1, L[i]);
        adj[H[i][1] + 1].emplace_back(H[i][0] + 1, L[i]);
    }
 
    solve();
    return (ans > n - 1 ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'int get_sz(int, int)':
race.cpp:16:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for(auto [y, w] : adj[x]) {
      |              ^
race.cpp: In function 'int get_cen(int, int, int)':
race.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |     for(auto [y, w] : adj[x]) {
      |              ^
race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for(auto [y, w] : adj[x]) {
      |              ^
race.cpp: In function 'void solve(int, int)':
race.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     for(auto [d, w] : adj[c]) {
      |              ^
race.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for(auto [d, w] : adj[c]) {
      |              ^
race.cpp:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for(auto [d, w] : adj[c]) {
      |              ^

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