Submission #1104788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104788		anmattroi	Race (IOI11_race)	C++14	100 / 100	722 ms	45132 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define fi first
#define se second

#define maxn 200005

using namespace std;

typedef pair<int, int> ii;

int n, k;
vector<ii> adj[maxn];
int ds = INT_MAX;
int sz[maxn], tsz = 0, nho[maxn];

void resz(int u, int dad) {
    sz[u] = 1; ++tsz;
    for (auto [v, w] : adj[u]) {
        if (v == dad || nho[v]) continue;
        resz(v, u);
        sz[u] += sz[v];
    }
}

int find_centroid(int u, int dad) {
    for (auto [v, w] : adj[u]) {
        if (v != dad && !nho[v] && sz[v] > tsz/2) return find_centroid(v, u);
    }
    return u;
}

map<int, int> dis;

void dfs(int u, int dad, int l, int depth) {
    if (l > k) return;
    int h = k-l;
    if (dis.count(h)) ds = min(ds, dis[h] + depth);
    for (auto [v, w] : adj[u]) {
        if (v == dad || nho[v]) continue;
        dfs(v, u, l+w, depth+1);
    }
}

void refs(int u, int dad, int l, int depth) {
    if (l > k) return;
    if (dis.count(l)) dis[l] = min(dis[l], depth);
    else dis[l] = depth;

    for (auto [v, w] : adj[u]) {
        if (v == dad || nho[v]) continue;
        refs(v, u, l+w, depth+1);
    }
}

void dcp(int u) {
    tsz = 0;
    resz(u, 0);

    int C = find_centroid(u, 0); nho[C] = 1;

    dis.clear();

    dis[0] = 0;

    for (auto [v, w] : adj[C]) {
        if (nho[v]) continue;
        dfs(v, C, w, 1);
        refs(v, C, w, 1);
    }

    for (auto [v, w] : adj[C]) {
        if (!nho[v]) dcp(v);
    }

}

int best_path(int N, int K, int H[][2], int L[]){
    n = N;
    k = K;
    ds = INT_MAX;
    for (int i = 0; i < N-1; i++) {
        int u = H[i][0], v = H[i][1], l = L[i];
        ++u; ++v;
        adj[u].emplace_back(v, l);
        adj[v].emplace_back(u, l);
    }
    dcp(1);
    for (int i = 1; i <= n; i++) {adj[i].clear(); nho[i] = 0;}
    return (ds == INT_MAX ? -1 : ds);
}

Compilation message (stderr)

race.cpp: In function 'void resz(int, int)':
race.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for (auto [v, w] : adj[u]) {
      |               ^
race.cpp: In function 'int find_centroid(int, int)':
race.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for (auto [v, w] : adj[u]) {
      |               ^
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:39:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for (auto [v, w] : adj[u]) {
      |               ^
race.cpp: In function 'void refs(int, int, int, int)':
race.cpp:50:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |     for (auto [v, w] : adj[u]) {
      |               ^
race.cpp: In function 'void dcp(int)':
race.cpp:66:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for (auto [v, w] : adj[C]) {
      |               ^
race.cpp:72:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for (auto [v, w] : adj[C]) {
      |               ^

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