Submission #255133

#	Time	Username	Problem	Language	Result	Execution time	Memory
255133		SamAnd	Race (IOI11_race)	C++17	100 / 100	1330 ms	33724 KiB

race

#include "race.h"
//#define "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
typedef long long ll;
const int N = 200005, K = 1000006;

int n, k;
vector<pair<int, int> > g[N];

int ans;

bool c[N];

int q[N];
void dfs0(int x, int p)
{
    q[x] = 1;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        if (h == p || c[h])
            continue;
        dfs0(h, x);
        q[x] += q[h];
    }
}

int dfsc(int x, int p, int xx)
{
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        if (h == p || c[h])
            continue;
        if (q[h] > q[xx] / 2)
            return dfsc(h, x, xx);
    }
    return x;
}

int minu[K];

void dfs1(int x, int p, int d, int q)
{
    if (d > k)
        return;
    minu[d] = min(minu[d], q);
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        int hd = g[x][i].se;
        if (h == p || c[h])
            continue;
        dfs1(h, x, d + hd, q + 1);
    }
}

void dfs2(int x, int p, int d, int q)
{
    if (d > k)
        return;
    minu[d] = N;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        int hd = g[x][i].se;
        if (h == p || c[h])
            continue;
        dfs2(h, x, d + hd, q + 1);
    }
}

void dfs3(int x, int p, int d, int q)
{
    if (d > k)
        return;
    ans = min(ans, q + minu[k - d]);
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        int hd = g[x][i].se;
        if (h == p || c[h])
            continue;
        dfs3(h, x, d + hd, q + 1);
    }
}

void solvv(int r)
{
    minu[0] = 0;
    for (int i = 0; i < g[r].size(); ++i)
    {
        int x = g[r][i].fi;
        int d = g[r][i].se;
        if (c[x])
            continue;
        dfs3(x, r, d, 1);
        dfs1(x, r, d, 1);
    }
    dfs2(r, r, 0, 0);
    reverse(all(g[r]));
    minu[0] = 0;
    for (int i = 0; i < g[r].size(); ++i)
    {
        int x = g[r][i].fi;
        int d = g[r][i].se;
        if (c[x])
            continue;
        dfs3(x, r, d, 1);
        dfs1(x, r, d, 1);
    }
    dfs2(r, r, 0, 0);
}

void solv()
{
    ans = N;

    for (int i = 0; i <= k; ++i)
        minu[i] = N;

    queue<int> q;
    q.push(1);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        dfs0(x, x);
        x = dfsc(x, x, x);
        solvv(x);
        c[x] = true;
        for (int i = 0; i < g[x].size(); ++i)
        {
            int h = g[x][i].fi;
            if (!c[h])
                q.push(h);
        }
    }

    if (ans == N)
        ans = -1;
}

int best_path(int n, int k, int H[][2], int L[])
{
    ::n = n;
    ::k = k;
    for (int i = 0; i < n - 1; ++i)
    {
        int x = H[i][0];
        int y = H[i][1];
        int z = L[i];
        ++x;
        ++y;
        g[x].push_back(m_p(y, z));
        g[y].push_back(m_p(x, z));
    }
    solv();
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs0(int, int)':
race.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
race.cpp: In function 'int dfsc(int, int, int)':
race.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void dfs1(int, int, int, int)':
race.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void dfs2(int, int, int, int)':
race.cpp:69:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void dfs3(int, int, int, int)':
race.cpp:84:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void solvv(int)':
race.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[r].size(); ++i)
                     ~~^~~~~~~~~~~~~
race.cpp:109:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[r].size(); ++i)
                     ~~^~~~~~~~~~~~~
race.cpp: In function 'void solv()':
race.cpp:138:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[x].size(); ++i)
                         ~~^~~~~~~~~~~~~

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