oj.uz

답안 #98936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98936 2019-02-27T15:25:11 Z Hideo 경주 (Race) (IOI11_race) C++14
0 / 100
 32 ms 17792 KB 
#include "race.h"
#include <bits/stdc++.h>
//#include "grader.cpp"

using namespace std;

#define mk make_pair
#define pb push_back
#define sc second
#define fr first
#define pii pair < int, int >
#define vii vector < pii >

const int MAXN = 2e5 + 7;
const int MAXK = 1e6 + 7;
const int INF = 1e9 + 7;

int ans = INF, k;
int st[MAXK], h[MAXN], del[MAXN];

vii g[MAXN];

void dfs (int v, int p = -1){
    h[v] = 1;
    for (pii to : g[v])
        if (to.fr != p && !del[to.fr])
            dfs(to.fr, v);
    if (p != -1)
        h[p] += h[v];
}

int centroid (int v){
    dfs(v);
    bool ok = false;
    int c = v, pr = 0;
    while (ok){
        ok = false;
        for (pii to : g[c]){
            if (to.fr != pr && !del[to.fr] && h[to.fr] * 2 >= h[v]){
                pr = c;
                c = to.fr;
                ok = true;
                break;
            }
        }
    }
    return c;
}

void findAns (int v, int p, int l, int d = 1){
    if (k > l && st[k - l])
        ans = min(ans, d + st[k - l]);
    if (k == l)
        ans = min(ans, d);
    for (pii to : g[v])
        if (to.fr != p && !del[to.fr])
            findAns (to.fr, v, l + to.sc, d + 1);
}

void upd (int v, int p, int l, int d = 1){
    if (st[l] && k >= l)
        st[l] = min(st[l], d);
    else if (k >= l)
        st[l] = d;
    for (pii to : g[v])
        if (to.fr != p && !del[to.fr])
            upd(to.fr, v, l + to.sc, d + 1);
}

void calc (int v = 0){
    v = centroid(v);
    del[v] = 1;
    memset(st, 0, sizeof(st));
    for (pii to : g[v]){
        if (!del[to.fr]){
            findAns(to.fr, v, to.sc);
            upd(to.fr, v, to.sc);
        }
    }
    for (pii to : g[v])
        if (!del[to.fr])
            calc (to.fr);
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for (int i = 0; i < N - 1; i++){
        g[H[i][0]].pb(mk(H[i][1], L[i]));
        g[H[i][1]].pb(mk(H[i][0], L[i]));
    }
    calc();
    if (ans == INF)
        return -1;
    return ans;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 8960 KB Output is correct
2 Correct 29 ms 8960 KB Output is correct
3 Correct 30 ms 8960 KB Output is correct
4 Correct 32 ms 8960 KB Output is correct
5 Runtime error 23 ms 17792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 8960 KB Output is correct
2 Correct 29 ms 8960 KB Output is correct
3 Correct 30 ms 8960 KB Output is correct
4 Correct 32 ms 8960 KB Output is correct
5 Runtime error 23 ms 17792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 8960 KB Output is correct
2 Correct 29 ms 8960 KB Output is correct
3 Correct 30 ms 8960 KB Output is correct
4 Correct 32 ms 8960 KB Output is correct
5 Runtime error 23 ms 17792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 8960 KB Output is correct
2 Correct 29 ms 8960 KB Output is correct
3 Correct 30 ms 8960 KB Output is correct
4 Correct 32 ms 8960 KB Output is correct
5 Runtime error 23 ms 17792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -