제출 #1317837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317837		Ekber_Ekber	경주 (Race) (IOI11_race)	C++20	0 / 100	2 ms	1848 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

constexpr int MAX = 2e+5 + 1, INF = 2e+9, MOD = 1e+9 + 7, K = 28;
int k;
vector <pair<int, int>> g[MAX+2];
vector <int> st(MAX+2), is(MAX+2);
vector <pair<int, int>> dis;
map <int, int> mx;
int res=-1;

void dfs(int u, int c=-1) {
    st[u] = 1;
    for (auto &i : g[u]) {
        if (i.ff == c || is[i.ff]) continue;
        dfs(i.ff, u);
        st[u] += st[i.ff];
    }
}

int get(int u, int s, int c=-1) {
    for (auto &i : g[u]) {
        if (i.ff == c || is[i.ff]) continue;
        if (st[i.ff] * 2 > s) return get(i.ff, s, u);
    }
    return u;
}

void dist(int u, int lv=0, int w=0, int c=-1) {
    if (w <= k) dis.pb({w, lv});
    for (auto &i : g[u]) {
        if (i.ff == c || is[i.ff]) continue;
        dist(i.ff, lv+1, w+i.ss, u);
    }
}

void build(int u) {
    dfs(u);
    int c = get(u, st[u]);
    is[c] = 1;
    mx.clear();
    for (auto &i : g[c]) {
        dis.clear();
        dist(i.ff, 1, i.ss);
        for (auto &j : dis) {
            if (mx.find(k-j.ff) == mx.end()) continue;
            res = max(res, mx[k-j.ff] + j.ss);
        }
        for (auto &j : dis) {
            mx[j.ff] = max(mx[j.ff], j.ss);
        }
    }
}

int best_path(int n, int K, int H[][2], int L[]) {
    k = K;
    for (int i = 0; i < n; i++) {
        g[H[i][0]].pb({H[i][1], L[i]});
        g[H[i][1]].pb({H[i][0], L[i]});
    }
    build(1);
    return res;
}

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