제출 #297163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297163		Kastanda	경주 (Race) (IOI11_race)	C++11	100 / 100	1018 ms	41488 KiB

race

/*
    Take me to church
    I'll worship like a dog at the shrine of your lies
    I'll tell you my sins and you can sharpen your knife
    Offer me that deathless death
    Good God, let me give you my life
*/
#include<bits/stdc++.h>
#include "race.h"
#define x first
#define y second
using namespace std;
const int N = 200005, MXK = 2000006;
int n, k, Mn = N, M[N], SZ[N], qu[N], H[N], D[N], B[MXK];
vector < pair < int , int > > Adj[N];
vector < int > A;
void DFSSZ(int v, int p = -1)
{
    SZ[v] = 1;
    for (auto u : Adj[v])
        if (!M[u.x] && u.x != p)
            DFSSZ(u.x, v), SZ[v] += SZ[u.x];
}
inline int Centroid(int v)
{
    DFSSZ(v);
    int _n = SZ[v], w = 1, p = -1;
    while (w)
    {
        w = 0;
        for (auto u : Adj[v])
            if (!M[u.x] && u.x != p && SZ[u.x] * 2 > _n)
                {p = v; v = u.x; w = 1; break;}
    }
    return (v);
}
void DFS(int v, int p)
{
    A.push_back(v);
    if (D[v] <= k)
        Mn = min(Mn, H[v] + B[k - D[v]]);
    for (auto u : Adj[v])
        if (!M[u.x] && u.x != p)
            H[u.x] = H[v] + 1, D[u.x] = min(D[v] + u.y, MXK - 2), DFS(u.x, v);
}
void UNDFS(int v, int p)
{
    B[D[v]] = B[MXK - 1];
    for (auto u : Adj[v])
        if (!M[u.x] && u.x != p)
            UNDFS(u.x, v);
}
inline void Solve(int v)
{
    H[v] = D[v] = 0;
    for (auto u : Adj[v])
        if (!M[u.x])
        {
            H[u.x] = H[v] + 1;
            D[u.x] = D[v] + u.y;
            DFS(u.x, v);
            for (int w : A)
                B[D[w]] = min(B[D[w]], H[w]);
            A.clear();
        }
    for (auto u : Adj[v])
        if (!M[u.x])
            UNDFS(u.x, v);
}
inline void Decompose()
{
    int l = 0, r = 0;
    qu[r ++] = 0;
    while (r - l)
    {
        int v = Centroid(qu[l ++]);
        Solve(v); M[v] = 1;
        for (auto u : Adj[v])
            if (!M[u.x])
                qu[r ++] = u.x;
    }
}
int best_path(int _n, int _k, int _E[200000][2], int _L[200000])
{
    n = _n; k = _k;
    //cin >> n >> k;
    memset(B, 63, sizeof(B)); B[0] = 0;
    for (int i = 0; i < n - 1; i ++)
    {
        Adj[_E[i][0]].push_back({_E[i][1], _L[i]});
        Adj[_E[i][1]].push_back({_E[i][0], _L[i]});
        //int a, b, c;
        //cin >> a >> b >> c;
        //Adj[a].push_back({b, c});
        //Adj[b].push_back({a, c});
    }
    int l = 0, r = 0;
    Decompose();
    if (Mn == N)
        Mn = -1;
    //printf("%d\n", Mn);
    //return 0;
    return (Mn);
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:97:9: warning: unused variable 'l' [-Wunused-variable]
   97 |     int l = 0, r = 0;
      |         ^
race.cpp:97:16: warning: unused variable 'r' [-Wunused-variable]
   97 |     int l = 0, r = 0;
      |                ^

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