Submission #625011

#	Time	Username	Problem	Language	Result	Execution time	Memory
625011		Netr	Race (IOI11_race)	C++14	0 / 100	3064 ms	4948 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pi;

#define lsb(x) (x&(-x))
#define fs first
#define sd second
#define mp make_pair
#define pb push_back

#ifdef DEBUG
#define D(x...) printf(x);
#else
#define D(x...)
#endif

const ll MAXN = 2e5 + 5;
const ll INF = 1ll<<60;

ll N, K, sz[MAXN], sum[MAXN], dist[MAXN], ans = INF;
vector<pi> adj[MAXN];
map<ll, ll> *len[MAXN];

ll precomp(ll n, ll p, ll s, ll d){
    sz[n] = 1;
    sum[n] = s;
    dist[n] = d;
    for(auto &[e, w] : adj[n]){
        if(e == p) continue;
        sz[n] += precomp(e, n, s + w, d + 1);
    }
    return sz[n];
}

void dfs(ll n, ll p = 0){
    ll mx = -1, u = -1;
    
    for(auto &[e, w] : adj[n]){
        if(e == p) continue;
        if(sz[e] > mx){
            mx = sz[e];
            u = e;
        }
        dfs(e, n);
    }

    if(u == -1){
        len[n] = new map<ll, ll>();
    }else{
        len[n] = len[u];
    }

    (*len[n])[sum[n]] = dist[n];
    if(len[n]->count(K+sum[n])){
        ans = min(ans, (*len[n])[K+sum[n]] - dist[n]);
    }

    for(auto &[e, w] : adj[n]){
        if(e == p || e == u) continue;

        for(auto &[s, d] : *len[e]){
            if(len[n]->count(K-s+2*sum[n])){
                ans = min(ans, d + (*len[n])[K-s+2*sum[n]] - 2*dist[n]);
            }
            
            if(len[n]->count(s)){
                (*len[n])[s] = min((*len[n])[s], d);
            }else{
                (*len[n])[s] = d;
            }
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    for(ll i = 0; i < N-1; i++){
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][1], L[i]});
    }

    precomp(0, 0, 0, 0);
    dfs(0);

    if(ans == INF){
        return -1;
    }else{
        return ans;
    }
}

Compilation message (stderr)

race.cpp: In function 'll precomp(ll, ll, ll, ll)':
race.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto &[e, w] : adj[n]){
      |               ^
race.cpp: In function 'void dfs(ll, ll)':
race.cpp:41:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto &[e, w] : adj[n]){
      |               ^
race.cpp:61:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for(auto &[e, w] : adj[n]){
      |               ^
race.cpp:64:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         for(auto &[s, d] : *len[e]){
      |                   ^

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