Submission #1068248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068248		Kipras	Race (IOI11_race)	C++17	100 / 100	315 ms	80744 KiB

race

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

constexpr ll maxN = 2e5+10;
constexpr ll inf = 1e15;

vector<pair<ll, ll>> adj[maxN];
ll res = inf, k;

map<ll, ll> dfs(ll v, ll p, ll konst, ll dep) {

    map<ll, ll> mp;

    mp[konst]=dep;

    for(auto i : adj[v]) {
        if(i.first==p)continue;
        map<ll, ll> tmp = dfs(i.first, v, i.second+konst, dep+1);
        if(tmp.size()>mp.size())swap(mp, tmp);
        for(auto x : tmp) {
            ll val = x.first;
            ll dep1 = x.second;
            ll needed = k+2*konst-val;
            if(mp.count(needed)) {
                ll dep2 = mp[needed];
                res=min(res, dep1+dep2-2*dep);
            }
        }
        for(auto x : tmp) {
            if(!mp.count(x.first))mp[x.first]=x.second;
            else mp[x.first]=min(x.second, mp[x.first]);
        }
    }

    return mp;

}

int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    for(int i = 0; i < N-1; i++) {
        ll aa = H[i][0], bb = H[i][1];

        adj[aa].push_back({bb, L[i]});
        adj[bb].push_back({aa, L[i]});
    }

    dfs(0, -1, 0, 0);

    if(res==inf) {
        return -1;
    }

    return res;
}

/*int nn, kk;
int H[maxN][2];
int L[maxN];
int solution;

int main()
{
    cin>>nn>>kk;
    for(int i = 0; i < nn-1; i++) {
        cin>>H[i][0]>>H[i][1];
    }
    for(int i = 0; i < nn-1; i++) {
        cin>>L[i];
    }
    cout<<best_path(nn,kk,H,L);

    return 0;
}
*/

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