Submission #931311

#	Time	Username	Problem	Language	Result	Execution time	Memory
931311		Regulus	Race (IOI11_race)	C++17	21 / 100	306 ms	23132 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 INF = 2e9;
int K, ans = INF, dis[N], dep[N], mxs[N], rt, sz[N], cnt;
bool vis[N];
vector<pll> g[N];
map<ll, int> mp, tmp;

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(map<ll, int> &mp, pll p)
{
    if (mp.count(p.F)) mp[p.F] = min(mp[p.F], (int)p.S);
    else mp[p.F] = p.S;
}

inline void dfs2(int x, int pre)
{
    push(tmp, 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;
    mp.clear(); mp[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;
        tmp.clear(); dfs2(v, x);
        for (auto p : tmp)
            if (mp.count(K - p.F)) ans = min(ans, p.S + mp[K - p.F]);
        for (auto p : tmp) push(mp, p);
    }
}

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;
    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:77:22: warning: unused variable 'w' [-Wunused-variable]
   77 |         int v = p.F, w = p.S;
      |                      ^

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