Submission #1083561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083561		Namviet2704	Race (IOI11_race)	C++17	43 / 100	793 ms	83424 KiB

race

#include <bits/stdc++.h>
//#include "race.h"
#define ll long long
#define fi first
#define se second
#define pii pair<ll, ll>

using namespace std;

const int N = 2e5 + 5;

ll n, k, ans = 1e9;
vector<pii> vt[N];
ll in[N], out[N], pos[N], sz[N];
pair<ll, int> h[N];
int cnt = 0;

void dfs(int u, int p)
{
    in[u] = ++cnt;
    pos[cnt] = u;
    sz[u] = 1;
    for(auto v : vt[u])
    {
        if(v.fi == p)
            continue;
        h[v.fi].fi = h[u].fi + v.se;
        h[v.fi].se = h[u].se + 1;
        dfs(v.fi, u);
        sz[u] += sz[v.fi];
    }
    out[u] = cnt;
}

map<ll, pii> mp;

void add(int u)
{
    for(int i = in[u]; i <= out[u]; i++)
    {
        pii tmp = mp[h[pos[i]].fi];
        if(tmp.fi == 0 || tmp.fi < h[pos[i]].se)
            mp[h[pos[i]].fi] = {h[pos[i]].se, pos[i]};
    }
}

void del(int u)
{
    for(int i = in[u]; i <= out[u]; i++)
        mp[h[pos[i]].fi] = {0, 0};
}

void solve(int u, int p)
{
    pair<int, int> big = {0, -1};
    for(auto v : vt[u])
        if(v.fi != p)
            big = max(big, {sz[v.fi], v.fi});
    for(auto v : vt[u])
    {
        if(v.fi == big.se || v.fi == p)
            continue;
        solve(v.fi, u);
        del(v.fi);
    }
    if(big.se != -1)
        solve(big.se, u);
    for(auto v : vt[u])
        if(v.fi != big.se && v.fi != p)
            add(v.fi);
    mp[h[u].fi] = {h[u].se, u};
    for(auto j : vt[u])
    {
        if(j.fi != big.se && j.fi != p)
            for(int i = in[j.fi]; i <= out[j.fi]; i++)
            {
                int v = pos[i];
                ll tmp = h[u].fi + k - (h[v].fi - h[u].fi);
                pii huhu = mp[tmp];
                if(huhu.fi == 0)
                    continue;
                int haha = huhu.se;
                if(out[haha] < in[v] || out[v] < in[haha] || v == u)
                    ans = min(ans, huhu.fi - h[u].se + h[v].se - h[u].se);
            }
    }
    pii huhu = mp[h[u].fi + k];
    if(huhu.fi == 0)
        return;
    ans = min(ans, huhu.fi - h[u].se);
    return;
}

int best_path(int m, int g, int h[][2], int l[])
{
    n = m;
    k = g;
    for(int i = 0; i < n - 1; i++)
    {
        vt[h[i][0]].push_back({h[i][1], l[i]});
        vt[h[i][1]].push_back({h[i][0], l[i]});
    }
    dfs(0, -1);
    solve(0, -1);
    if(ans == (int) 1e9)
        return -1;
    return ans;
}

//int main()
//{
////    freopen(task".inp", "r", stdin);
////    freopen(task".out", "w", stdout);
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL), cout.tie(NULL);
//    cin >> n >> k;
//    for(int i = 1; i < n; i++)
//    {
//        int x, y, w;
//        cin >> x >> y >> w;
//        vt[x].push_back({y, w});
//        vt[y].push_back({x, w});
//    }
//    dfs(0, -1);
//    cout << best_path();
//    return 0;
//}

/*
4 3
0 1 1
1 2 2
1 3 4
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

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