Submission #551472

#	Time	Username	Problem	Language	Result	Execution time	Memory
551472		Leo121	Race (IOI11_race)	C++14	100 / 100	401 ms	92848 KiB

race

#include <bits/stdc++.h>
#include "race.h"

#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define foru(i, v) for(auto i : v)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int maxn = 2e5;
map<ll, int> *cnt[maxn];
int sz[maxn];
int prof[maxn];
ll tam[maxn];
vpii tree[maxn];
int res, k;

void dfs(int u, int p){
    int mx = -1, bigchild = -1;
    sz[u] = 1;
    foru(v, tree[u]){
        if(v.fi != p){
            prof[v.fi] = prof[u] + 1;
            tam[v.fi] = tam[u] + (ll) v.se;
            dfs(v.fi, u);
            sz[u] += sz[v.fi];
            if(sz[v.fi] > mx){
                mx = sz[v.fi];
                bigchild = v.fi;
            }
        }
    }
    cnt[u] = (bigchild == -1) ? new map<ll, int>   : cnt[bigchild];
    ll distancia;
    foru(v, tree[u]){
        if(v.fi != p && v.fi != bigchild){
            foru(i, *cnt[v.fi]){
                distancia = i.fi;
                distancia -= tam[u];
                if((*cnt[u]).count(tam[u] + ((ll) k - distancia))){
                    res = (res == -1) ? ((*cnt[u])[tam[u] + ((ll) k - distancia)] - prof[u]) + (i.se - prof[u]) : min(res, ((*cnt[u])[tam[u] + ((ll) k - distancia)] - prof[u]) + (i.se - prof[u]));
                }
            }
            foru(i, *cnt[v.fi]){
                if((*cnt[u]).count(i.first)){
                    (*cnt[u])[i.first] = min((*cnt[u])[i.first], i.second);
                    continue;
                }
                (*cnt[u])[i.first] = i.second;
            }
        }
    }
    if((*cnt[u]).count((ll) k + tam[u])){
        res = (res == -1) ? ((*cnt[u])[tam[u] + (ll) k] - prof[u]) : min(res, ((*cnt[u])[tam[u] + (ll) k] - prof[u]));
    }
    (*cnt[u])[tam[u]] = prof[u];
}

int best_path(int N, int K, int H[][2], int L[]){
    forn(i, 0, N - 2){
        tree[H[i][0]].pb(mp(H[i][1], L[i]));
        tree[H[i][1]].pb(mp(H[i][0], L[i]));
    }
    k = K;
    res = -1;
    dfs(0, 0);
    return res;
}

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