Submission #1083485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083485		Namviet2704	Race (IOI11_race)	C++17	21 / 100	3066 ms	26456 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
#pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>

using namespace std;

const int N = 2e5 + 5;

int n, k, ans = 1e9;
vector<pii> vt[N];
int in[N], out[N], pos[N], sz[N], kq[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)
            mp[h[pos[i]].fi] = {h[pos[i]].se, pos[i]};
        else
            mp[h[pos[i]].fi] = min(tmp, {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(int i = in[u]; i <= out[u]; i++)
    {
        if(big.se != -1 && in[big.se] <= i && i <= out[big.se])
            continue;
        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, h[haha].se - h[u].se + h[v].se - 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: 0 / 22
• Subtask 4: 0 / 57