Submission #164824

#	Time	Username	Problem	Language	Result	Execution time	Memory
164824		arnold518	경주 (Race) (IOI11_race)	C++14	100 / 100	706 ms	34328 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int MAXK = 1e6;

int N, K;
vector<pii> adj[MAXN+10];

bool del[MAXN+10];
int sz[MAXN+10], ans=987654321;

void getsz(int now, int bef)
{
    sz[now]=1;
    for(auto nxt : adj[now])
    {
        if(nxt.first==bef) continue;
        if(del[nxt.first]) continue;
        getsz(nxt.first, now);
        sz[now]+=sz[nxt.first];
    }
}

int getcen(int now, int bef, int tot)
{
    for(auto nxt : adj[now])
    {
        if(nxt.first==bef) continue;
        if(del[nxt.first]) continue;
        if(sz[nxt.first]>tot/2) return getcen(nxt.first, now, tot);
    }
    return now;
}

int M[MAXK+10];
vector<int> V;

void dfs1(int now, int bef, ll dist, int road)
{
    if(K-dist>=0) ans=min(ans, M[K-dist]+road);
    for(auto nxt : adj[now])
    {
        if(nxt.first==bef) continue;
        if(del[nxt.first]) continue;
        dfs1(nxt.first, now, dist+nxt.second, road+1);
    }
}

void dfs2(int now, int bef, ll dist, int road)
{
    if(dist<=K) M[dist]=min(M[dist], road), V.push_back(dist);
    for(auto nxt : adj[now])
    {
        if(nxt.first==bef) continue;
        if(del[nxt.first]) continue;
        dfs2(nxt.first, now, dist+nxt.second, road+1);
    }
}

void decomp(int now)
{
    getsz(now, now);
    now=getcen(now, now, sz[now]);
    del[now]=true;

    M[0]=0; V.clear();
    for(auto nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        dfs1(nxt.first, nxt.first, nxt.second, 1);
        dfs2(nxt.first, nxt.first, nxt.second, 1);
    }
    for(auto it : V) M[it]=987654321;

    for(auto nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        decomp(nxt.first);
    }
}

int best_path(int _N, int _K, int H[][2], int L[])
{
    int i, j;
    N=_N; K=_K;
    for(i=0; i<N-1; i++)
    {
        int u, v, w;
        u=H[i][0]+1; v=H[i][1]+1; w=L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    for(i=0; i<=K; i++) M[i]=987654321;
    decomp(1);
    if(ans==987654321) ans=-1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:90:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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