제출 #883874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883874		chanhchuong123	공장들 (JOI14_factories)	C++14	100 / 100	4525 ms	197392 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define task ""
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const long long INF = 1e18 + 7;
const int MAX = 500005;
int n, q;
int timer;
int h[MAX];
int fr[MAX];
int to[MAX];
int co[MAX];
int sz[MAX];
int tin[MAX];
int par[MAX];
bool rem[MAX];
long long dep[MAX];
long long dist[MAX];
int dp[20][MAX << 1];
vector<int> adj[MAX];
#define COMBINE(u, v) (h[(u)] <= h[(v)] ? (u) : (v))

void dfs(int u, int p) {
    dp[0][timer] = u;
    tin[u] = timer++;
    for (int &id: adj[u]) {
        int v = fr[id] ^ to[id] ^ u;
        if (v != p && rem[v] == 0) {
            dep[v] = dep[u] + co[id];
            h[v] = h[u] + 1;
            dfs(v, u);
            dp[0][timer++] = u;
        }
    }
}

int LCA(int u, int v) {
    int l = tin[u], r = tin[v]; if (l > r) swap(l, r);
    int k = 31 - __builtin_clz(r - l + 1);
    return COMBINE(dp[k][l], dp[k][r - (1 << k) + 1]);
}

long long DIST(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
}

int dfsSZ(int u, int p) {
    sz[u] = 1;
    for (int &id: adj[u]) {
        int v = fr[id] ^ to[id] ^ u;
        if (v != p && rem[v] == 0) {
            sz[u] += dfsSZ(v, u);
        }
    }
    return sz[u];
}

int findCentroid(int u, int p, int n) {
    for (int &id: adj[u]) {
        int v = fr[id] ^ to[id] ^ u;
        if (v != p && rem[v] == 0) {
            if ((sz[v] << 1) > n)
                return findCentroid(v, u, n);
        }
    }
    return u;
}

void solve(int u, int p) {
    int c = findCentroid(u, p, dfsSZ(u, p));
    dist[c] = INF;
    rem[c] = true;
    par[c] = p;
    for (int &id: adj[c]) {
        int v = fr[id] ^ to[id] ^ c;
        if (v != p && rem[v] == 0) {
            solve(v, c);
        }
    }
}

void Init(int _n, int _a[], int _b[], int _d[]) {
    n = _n;
    for (int i = 0; i < n - 1; ++i) {
        fr[i] = _a[i];
        to[i] = _b[i];
        co[i] = _d[i];
        adj[fr[i]].push_back(i);
        adj[to[i]].push_back(i);
    }
    dfs(0,   -1);
    for (int j = 1; (1 << j) <= timer; ++j) {
        for (int i = 0; i + (1 << j) - 1 <= timer - 1; ++i)
            dp[j][i] = COMBINE(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
    }
    solve(0, -1);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++i) {
        for (int cur = X[i]; cur != -1; cur = par[cur])
                dist[cur] = min(dist[cur], DIST(X[i], cur));
    }
    long long res = INF;
    for (int i = 0; i < T; ++i) {
        for (int cur = Y[i]; cur != -1; cur = par[cur])
                res = min(res, dist[cur] + DIST(Y[i], cur));
    }
    for (int i = 0; i < S; ++i) {
        for (int cur = X[i]; cur != -1; cur = par[cur])
            dist[cur] = INF;
    }
    return res;
}

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

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:97:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   97 |             dp[j][i] = COMBINE(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
      |                                                                  ~~^~~
factories.cpp:24:37: note: in definition of macro 'COMBINE'
   24 | #define COMBINE(u, v) (h[(u)] <= h[(v)] ? (u) : (v))
      |                                     ^
factories.cpp:97:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   97 |             dp[j][i] = COMBINE(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
      |                                                                  ~~^~~
factories.cpp:24:50: note: in definition of macro 'COMBINE'
   24 | #define COMBINE(u, v) (h[(u)] <= h[(v)] ? (u) : (v))
      |                                                  ^

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67