Submission #500235

#	Time	Username	Problem	Language	Result	Execution time	Memory
500235		danikoynov	Race (IOI11_race)	C++14	100 / 100	2506 ms	80636 KiB

race

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 10, maxk = 1e6 + 10, inf = 1e9;

vector < pair < ll, ll > > g[maxn];
ll lvl[maxn], depth[maxn], sub[maxn];
unordered_map < ll, ll > mp, vis;
void pre_dfs(ll v, ll par)
{
    sub[v] = 1;
    for (ll i = 0; i < g[v].size(); i ++)
    {
        ll u = g[v][i].first;
        if (u == par)
            continue;
        lvl[u] = lvl[v] + 1;
        depth[u] = depth[v] + g[v][i].second;
        pre_dfs(u, v);
        sub[v] += sub[u];
    }
}

ll cnt[maxk], ans, k;
void check_dfs(ll v, ll p, ll root)
{
    ll len = (k + depth[root]) - depth[v] + depth[root];
    ///cout << depth[v] << " " << depth[root] << " " << len << endl;
    if (vis[len])
    {
        ans = min(ans, lvl[v] - lvl[root] + mp[len] - lvl[root]);
        ///cout << lvl[v] << " - " << lvl[root] << " - " << mp[len] << endl;
    }
    for (ll i = 0; i < g[v].size(); i ++)
    {
        ll u = g[v][i].first;
        if (u == p)
            continue;
        check_dfs(u, v, root);
    }
}

vector < ll > path;
void add_dfs(ll v, ll p, ll root)
{
    ll len = depth[v];
    if (vis[len])
        mp[len] = min(mp[len], lvl[v]);
    else
    {
        vis[len] = 1;
        mp[len] = lvl[v];
    }
    for (ll i = 0; i < g[v].size(); i ++)
    {
        ll u = g[v][i].first;
        if (u == p)
            continue;
        add_dfs(u, v, root);
    }
}
void dfs(ll v, ll p, bool big, ll last_depth)
{
    ll mx = -1, new_depth = 0;
    for (ll i = 0; i < g[v].size(); i ++)
    {
        ll u = g[v][i].first;
        if (u == p)
            continue;
        if (mx == -1 || sub[u] > sub[mx])
            mx = u, new_depth = depth[u] - depth[v];
    }

    for (ll i = 0; i < g[v].size(); i ++)
    {
        ll u = g[v][i].first;
        if (u == p || u == mx)
            continue;
        dfs(u, v, false, 0);
    }

    if (mx != -1)
    {
        dfs(mx, v, true, new_depth);
    }

    vis[depth[v]] = 1;
    mp[depth[v]] = lvl[v];
    if (vis[depth[v] + k])
        ans = min(ans, mp[depth[v] + k] - lvl[v]);

    for (ll i = 0; i < g[v].size(); i ++)
    {
        ll u = g[v][i].first;
        if (u == p || u == mx)
            continue;
        check_dfs(u, v, v);
        add_dfs(u, v, v);
    }

    /**cout << v << endl;
    for (ll i = 0; i <= k; i ++)
        cout << cnt[i] << " ";
    cout << endl;*/

    if (!big)
    {
        vis.clear();
        mp.clear();
    }



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

    pre_dfs(0, -1);
    for (ll i = 0; i <= K; i ++)
        cnt[i] = inf;
    ans = inf;
    dfs(0, -1, 1, 0);
    if (ans == inf)
        return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void pre_dfs(ll, ll)':
race.cpp:13:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (ll i = 0; i < g[v].size(); i ++)
      |                    ~~^~~~~~~~~~~~~
race.cpp: In function 'void check_dfs(ll, ll, ll)':
race.cpp:35:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (ll i = 0; i < g[v].size(); i ++)
      |                    ~~^~~~~~~~~~~~~
race.cpp: In function 'void add_dfs(ll, ll, ll)':
race.cpp:55:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (ll i = 0; i < g[v].size(); i ++)
      |                    ~~^~~~~~~~~~~~~
race.cpp: In function 'void dfs(ll, ll, bool, ll)':
race.cpp:66:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (ll i = 0; i < g[v].size(); i ++)
      |                    ~~^~~~~~~~~~~~~
race.cpp:75:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (ll i = 0; i < g[v].size(); i ++)
      |                    ~~^~~~~~~~~~~~~
race.cpp:93:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (ll i = 0; i < g[v].size(); i ++)
      |                    ~~^~~~~~~~~~~~~

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