Submission #111787

#	Time	Username	Problem	Language	Result	Execution time	Memory
111787		Mercenary	Race (IOI11_race)	C++14	100 / 100	667 ms	74836 KiB

race

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

using namespace std;
#define taskname "TEST"
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 2e5 + 5;
typedef pair<int,int> tpair;
int n , sz[maxn] , h[maxn] , k;
int res = maxn;
vector<tpair> v[maxn];
unordered_map<ll,int> *vec[maxn];
ll dep[maxn];
void DFS1(int u , int p)
{
    sz[u] = 1;
    for(tpair c : v[u])
    {
        if(p == c.first)continue;
        h[c.first] = h[u] + 1;
        dep[c.first] = dep[u] + c.second;
        DFS1(c.first,u);
        sz[u] += sz[c.first];
    }
}
void add(unordered_map<ll,int> & s , int h1 , ll d1 , int& h , ll& d , int type)
{
    if(type == 1)
    {
        ll need = k - d1 + 2 * d;
        if(!s.count(need))return;
        res = min(res ,s[need] + h1 - 2 * h);
    }
    else {
        if(!s.count(d1))
        {
            s[d1] = h1;
            return;
        }
        int tmp = s[d1];
        if(tmp > h1)s[d1] = h1;
    }
}
void DSU(int u , int p)
{
    int bigchild = -1;
    for(auto c : v[u])
        if(c.first != p && (bigchild == -1 || sz[bigchild] < sz[c.first]))
            bigchild = c.first;
    for(auto c : v[u])
        if(c.first != p && c.first != bigchild)
            DSU(c.first , u);
    if(bigchild != -1)
    {
        DSU(bigchild , u);
        vec[u] = vec[bigchild];
    }
    else vec[u] = new unordered_map<ll,int>;
    add(*vec[u] , h[u] , dep[u] , h[u] , dep[u] , 0);
    add(*vec[u] , h[u] , dep[u] , h[u] , dep[u] , 1);
    for(auto c : v[u])
        if(c.first != p && c.first != bigchild){
            for(auto d : (*vec[c.first]))
                add(*vec[u] , d.second , d.first , h[u] , dep[u] , 1);
            for(auto d : (*vec[c.first]))
                add(*vec[u] , d.second , d.first , h[u] , dep[u] , 0);
        }
}


int best_path(int N, int K, int H[][2], int L[])
{
    n = N;k = K;
    for(int i = 0 ; i < n - 1 ; ++i){
        int a = H[i][0] , b = H[i][1] , c = L[i];
        ++a;++b;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    DFS1(1 ,0);
    DSU(1 ,0);
    if(res == maxn)return -1;
    else return res;
}

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