oj.uz

답안 #129493

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129493 2019-07-12T09:51:51 Z arnold518 경주 (Race) (IOI11_race) C++14
0 / 100
 7 ms 5112 KB 
#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;

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

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

map<int, int> M;

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)
{
    if(M.count(K-len)) ans=min(ans, M[K-len]+dep);
    if(M.count(len)) M[len]=min(M[len], dep);
    else M[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);
    }
}

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

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

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

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

Compilation message

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

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -