제출 #164817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164817		arnold518	경주 (Race) (IOI11_race)	C++14	21 / 100	3024 ms	16240 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) getcen(nxt.first, now, tot);
    }
    return now;
}

map<ll, int> M, M2;

void dfs(int now, int bef, ll dist, int road)
{
    if(M.find(K-dist)!=M.end()) ans=min(ans, M[K-dist]+road);
    if(dist<=K)
    {
        if(M2.find(dist)!=M2.end()) M2[dist]=min(M2[dist], road);
        else M2[dist]=road;
    }
    for(auto nxt : adj[now])
    {
        if(nxt.first==bef) continue;
        if(del[nxt.first]) continue;
        dfs(nxt.first, now, dist+nxt.second, road+1);
    }
}

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

    M.clear();
    M[0]=0;
    for(auto nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        dfs(nxt.first, nxt.first, nxt.second, 1);
        for(auto it : M2)
        {
            if(M.find(it.first)!=M.end()) M[it.first]=min(M[it.first], it.second);
            else M[it.first]=it.second;
        }
        M2.clear();
    }

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

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});
    }

    decomp(1, 0);
    if(ans==987654321) ans=-1;
    return ans;
}

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

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

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