제출 #1360860

#제출 시각아이디문제언어결과실행 시간메모리
1360860vjudge1Roadside Advertisements (NOI17_roadsideadverts)C++17
100 / 100
57 ms13988 KiB

/*
    1. ???????? 5 ?????????????????????
    2. ?????????????????????????????? DFS ???????????????????????
    3. ???$Ans = \frac{1}{2} \sum_{i=1}^{k} dist(p_i, p_{i+1})$??? $p_{k+1} = p_1$?
    4. ?????????$dist(u, v) = dist[u] + dist[v] - 2 \times dist[LCA(u, v)]$?
    5. ????????? $O(V \log V)$??????? $O(k \log k)$????? $O(k \log V)$????? $O(V \log V + Q \log V)$?
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// #define int long long

const int N = 50005;
const int LOG = 17;

vector<int> adj[N];   // ???
vector<int> val[N];   // ??
int par[N][LOG + 1];  // ????
int dist[N];          // ??????????
int dep[N];           // ??
int dfn[N];           // Depth First Number, DFS ?
int timer;

// ??? DFS
void dfs(int u, int pre, int d, int w) {
    dep[u] = d;
    dist[u] = w;
    dfn[u] = ++timer;
    par[u][0] = pre;
    for (int i = 1; i <= LOG; i++) {
        par[u][i] = par[par[u][i - 1]][i - 1];
    }
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (v != pre) {
            dfs(v, u, d + 1, w + val[u][i]);
        }
    }
}

// ??????? LCA ??
int get_lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);

    // 1. ???????????
    int diff = dep[u] - dep[v];
    for (int i = 0; i <= LOG; i++) {
        if ((diff >> i) & 1) {
            u = par[u][i];
        }
    }

    if (u == v) return u;

    // 2. ??????
    for (int i = LOG; i >= 0; i--) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

// ?????????
int get_dist(int u, int v) {
    return dist[u] + dist[v] - 2 * dist[get_lca(u, v)];
}

// ? DFS ???
bool cmp(int a, int b) {
    return dfn[a] < dfn[b];
}

signed main() {

    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(v);
        val[u].push_back(w);
        adj[v].push_back(u);
        val[v].push_back(w);
    }

    // ????? 0 ~ V-1?DFS?0????????0???
    dfs(0, 0, 1, 0);

    int q;
    cin >> q;
    while (q--) {
        vector<int> p(5);
        for (int i = 0; i < 5; i++) cin >> p[i];

        sort(p.begin(), p.end(), cmp);

        int res = 0;
        for (int i = 0; i < 5; i++) {
            res += get_dist(p[i], p[(i + 1) % 5]);
        }
        cout << res / 2 << "\n";
    }

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…