Submission #500197

#	Time	Username	Problem	Language	Result	Execution time	Memory
500197		danikoynov	Race (IOI11_race)	C++14	0 / 100	7 ms	10000 KiB

race

#include<bits/stdc++.h>

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

vector < pair < int, int > > g[maxn];
int lvl[maxn], depth[maxn], sub[maxn];
void pre_dfs(int v, int par)
{
    sub[v] = 1;
    for (int i = 0; i < g[v].size(); i ++)
    {
        int 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];
    }
}

int cnt[maxk], ans, k;
void check_dfs(int v, int p, int root)
{
    int len = depth[v] - depth[root];
    if (len > k)
        return;
    if (cnt[k - len] + lvl[v] - lvl[root] < ans)
        ans = cnt[k - len] + lvl[v] - lvl[root];
    for (int i = 0; i < g[v].size(); i ++)
    {
        int u = g[v][i].first;
        if (u == p)
            continue;
        check_dfs(u, v, root);
    }
}

vector < int > path;
void add_dfs(int v, int p, int root)
{

       int len = depth[v] - depth[root];
    if (len > k)
        return;
    path.push_back(v);
    cnt[len] = min(cnt[len], lvl[v] - lvl[root]);
    for (int i = 0; i < g[v].size(); i ++)
    {
        int u = g[v][i].first;
        if (u == p)
            continue;
        add_dfs(u, v, root);
    }
}
void dfs(int v, int p, bool big, int last_depth)
{
    int mx = -1, new_depth = 0;
    for (int i = 0; i < g[v].size(); i ++)
    {
        int 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 (int i = 0; i < g[v].size(); i ++)
    {
        int 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);
    }

    cnt[0] = 0;
    path.push_back(v);
    for (int i = 0; i < g[v].size(); i ++)
    {
        int 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 (int i = 0; i <= k; i ++)
        cout << cnt[i] << " ";
    cout << endl;*/

    if (big)
    {
                for (int i = 0; i < path.size(); i ++)
        {
            int u = path[i];
            cnt[depth[u] - depth[v]] = inf;
        }

        for (int i = 0; i < path.size(); i ++)
        {
            int u = path[i];
            int len = depth[u] - depth[v] + last_depth;
            if (len == k)
                ans = min(ans, lvl[u] - lvl[v] + 1);
            cnt[len] = min(cnt[len], lvl[u] - lvl[v] + 1);
        }
    }
    else
    {
        for (int i = 0; i < path.size(); i ++)
        {
            int u = path[i];
            cnt[depth[u] - depth[v]] = inf;
        }
        path.clear();
    }

}
int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for (int 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 (int 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(int, int)':
race.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i = 0; i < g[v].size(); i ++)
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void check_dfs(int, int, int)':
race.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < g[v].size(); i ++)
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void add_dfs(int, int, int)':
race.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < g[v].size(); i ++)
      |                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, bool, int)':
race.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < g[v].size(); i ++)
      |                     ~~^~~~~~~~~~~~~
race.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0; i < g[v].size(); i ++)
      |                     ~~^~~~~~~~~~~~~
race.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i = 0; i < g[v].size(); i ++)
      |                     ~~^~~~~~~~~~~~~
race.cpp:100:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |                 for (int i = 0; i < path.size(); i ++)
      |                                 ~~^~~~~~~~~~~~~
race.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (int i = 0; i < path.size(); i ++)
      |                         ~~^~~~~~~~~~~~~
race.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for (int i = 0; i < path.size(); i ++)
      |                         ~~^~~~~~~~~~~~~

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