Submission #931332

#	Time	Username	Problem	Language	Result	Execution time	Memory
931332		Regulus	Race (IOI11_race)	C++17	0 / 100	11 ms	21340 KiB

race

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define bug(x) cerr << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
//#define TEST
const int N = 1e5+5;
const int Mxm = 1e6+5;
const int INF = 2e9;
int K, ans = INF, dis[N], dep[N], mxs[N], rt, sz[N], cnt, mn[Mxm], mn2[Mxm];
bool vis[N];
vector<pll> g[N];
vector<int> v, v2;

inline void find_rt(int x, int pre)
{
    sz[x] = 1, mxs[x] = 0;
    for (auto p : g[x])
    {
        int v = p.F;
        if (vis[v] || v == pre) continue;
        find_rt(v, x), sz[x] += sz[v];
        mxs[x] = max(mxs[x], sz[v]);
    }
    mxs[x] = max(mxs[x], cnt - sz[x]);
    if (mxs[x] < mxs[rt]) rt = x;
}

inline void push(pll p)
{
    if (p.F <= K) v2.pb(p.F);
    mn2[p.F] = min(mn2[p.F], (int)p.S);
}

inline void dfs2(int x, int pre)
{
    push(pll{dis[x], dep[x]});
    for (auto p : g[x])
    {
        int v = p.F, w = p.S;
        if (v == pre || vis[v]) continue;
        dis[v] = dis[x] + w, dep[v] = dep[x] + 1;
        dfs2(v, x);
    }
}

inline void calu(int x)
{
    dis[x] = dep[x] = 0;
    v.clear(); v.pb(0), mn[0] = 0;
    for (auto p : g[x])
    {
        int v = p.F, w = p.S;
        if (vis[v]) continue;
        dis[v] = dis[x] + w, dep[v] = dep[x] + 1;
        v2.clear(); dfs2(v, x);
        for (int d : v2)
        {
            if (d <= K) ans = min(ans, mn[K-d] + mn2[d]);
        }
        for (int d : v2)
        {
            if (d <= K)
            {
                mn[d] = min(mn[d], mn2[d]);
                mn2[d] = INF, ::v.pb(d);
            }
        }
    }
    for (int d : v) mn[d] = INF;
}

inline void solve(int x)
{
    vis[x] = 1;
    calu(x);
    for (auto p : g[x])
    {
        int v = p.F, w = p.S;
        if (vis[v]) continue;
        cnt = sz[v], mxs[rt = 0] = INF;
        find_rt(v, x);
        solve(rt);
    }
}

#ifndef TEST
int best_path(int n, int _k, int e[][2], int len[])
{
    K = _k;
    for (int i=0; i < n-1; ++i)
    {
        int x = e[i][0], y = e[i][1], w = len[i];
        ++x, ++y;
        g[x].pb(y, w), g[y].pb(x, w);
    }

    cnt = n, mxs[rt = 0] = INF;
    for (int i=0; i <= K; ++i) mn[i] = mn2[i] = INF;
    find_rt(1, 0);
    solve(rt);
    ans = (ans == INF)?-1 : ans;
    return ans;
}
#else
int main(void)
{ IO
    int n, i;

    cin >> n >> K;
    for (i=0; i < n-1; ++i)
    {
        int x, y, w; cin >> x >> y >> w, ++x, ++y;
        g[x].pb(y, w), g[y].pb(x, w);
    }

    cnt = n, mxs[rt = 0] = INF;
    find_rt(1, 0);
    solve(rt);
    ans = (ans == INF)?-1 : ans;
    cout << ans << '\n';

    return 0;
}
#endif

Compilation message (stderr)

race.cpp: In function 'void solve(int)':
race.cpp:88:22: warning: unused variable 'w' [-Wunused-variable]
   88 |         int v = p.F, w = p.S;
      |                      ^

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