제출 #129560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129560		arnold518	경주 (Race) (IOI11_race)	C++14	100 / 100	682 ms	36816 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;
const int INF = 987654321;

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

int sz[MAXN+10];
bool del[MAXN+10];
int M[MAXK+10];

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

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

void dfs(int now, int bef, int dep, int len, vector<pii>& V)
{
    V.push_back({len, dep});

    for(pii nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        if(nxt.first==bef) continue;
        if(len+nxt.second>K) continue;
        dfs(nxt.first, now, dep+1, len+nxt.second, V);
    }
}

void decomp(int now)
{
    int i, j;
    getsz(now, now);
    now=getcen(now, now, sz[now]);
    del[now]=true;
    vector<int> change;
    change.push_back(0);
    M[0]=0;

    for(pii nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        vector<pii> V;
        dfs(nxt.first, nxt.first, 1, nxt.second, V);

        for(i=0; i<V.size(); i++)
        {
            int len=V[i].first, dep=V[i].second;
            if(len>K) continue;
            change.push_back(len);
            ans=min(ans, M[K-len]+dep);
        }

        for(i=0; i<V.size(); i++)
        {
            int len=V[i].first, dep=V[i].second;
            if(len>K) continue;
            M[len]=min(M[len], dep);
        }
    }

    for(i=0; i<change.size(); i++) M[change[i]]=INF;

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

int best_path(int NN, int KK, int HH[][2], int LL[])
{
    int i, j;
    N=NN; K=KK;
    for(i=0; i+1<N; i++)
    {
        int u=HH[i][0], v=HH[i][1], w=LL[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for(i=0; i<=1000000; i++) M[i]=INF;

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

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

race.cpp: In function 'void decomp(int)':
race.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0; i<V.size(); i++)
                  ~^~~~~~~~~
race.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0; i<V.size(); i++)
                  ~^~~~~~~~~
race.cpp:88:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<change.size(); i++) M[change[i]]=INF;
              ~^~~~~~~~~~~~~~
race.cpp:58:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:99: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