제출 #639971

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

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
const ll oo = 1e18;
const int MAXN = 5e5 + 5;
const int Nx2 = 1e6 + 5;
int n, h[MAXN], a[Nx2][20], tin[MAXN], LOG[Nx2], s[MAXN], c[MAXN], p[MAXN], cnt = 0;
ll d[MAXN], f[MAXN];
vpi adj[MAXN];
void dfs(int u, int p) {
    a[++cnt][0] = u;
    EACH(j, adj[u]) {
        int v = j.st, w = j.nd;
        if (v == p) continue;
        d[v] = d[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
        a[++cnt][0] = u;
    }
}
int lca(int a, int b) {
    a = tin[a];
    b = tin[b];
    if (a > b) swap(a, b);
    int len = LOG[b - a + 1];
    int f = ::a[a][len], s = ::a[b - (1 << len) + 1][len];
    if (h[f] < h[s]) return f;
    return s;
}
ll dis(int a, int b) { return d[a] + d[b] - 2 * d[lca(a, b)]; }
void dfs1(int u, int p) {
    s[u] = 1;
    EACH(j, adj[u]) {
        int v = j.st;
        if (v == p || c[v]) continue;
        dfs1(v, u);
        s[u] += s[v];
    }
}
int fct(int u, int p, int s) {
    EACH(j, adj[u]) {
        int v = j.st;
        if (v == p || c[v]) continue;
        if (2 * ::s[v] > s) return fct(v, u, s);
    }
    return u;
}
void centroid(int u, int p) {
    dfs1(u, 0);
    int ct = fct(u, 0, s[u]);
    ::p[ct] = p;
    c[ct] = 1;
    EACH(j, adj[ct]) {
        int v = j.st;
        if (v == p || c[v]) continue;
        centroid(v, ct);
    }
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    FOR(i, 0, N - 2) {
        int u = A[i] + 1, v = B[i] + 1, w = D[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    dfs(1, 0);
    FOS(i, cnt, 1) tin[a[i][0]] = i;
    FOR(j, 1, 19)
    FOR(i, 1, cnt) {
        if (i + (1 << j) - 1 > cnt) break;
        int f = a[i][j - 1], s = a[i + (1 << (j - 1))][j - 1];
        if (h[f] < h[s]) a[i][j] = f;
        else a[i][j] = s;
    }
    FOR(i, 1, Nx2 - 1) LOG[i] = log2(i);
    centroid(1, 0);
    FOR(i, 1, n) f[i] = oo;
}
long long Query(int S, int X[], int T, int Y[]) {
    FOR(i, 0, S - 1) {
        int u = X[i] + 1, cur = u;
        WHILE(cur) {
            f[cur] = min(f[cur], dis(u, cur));
            cur = p[cur];
        }
    }
    ll rs = oo;
    FOR(i, 0, T - 1) {
        int u = Y[i] + 1, cur = u;
        WHILE(cur) {
            rs = min(rs, f[cur] + dis(u, cur));
            cur = p[cur];
        }
    }
    FOR(i, 0, S - 1) {
        int u = X[i] + 1, cur = u;
        WHILE(cur) {
            f[cur] = oo;
            cur = p[cur];
        }
    }
    return rs;
}

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

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
factories.cpp:46:5: note: in expansion of macro 'EACH'
   46 |     EACH(j, adj[u]) {
      |     ^~~~
factories.cpp: In function 'void dfs1(int, int)':
factories.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
factories.cpp:67:5: note: in expansion of macro 'EACH'
   67 |     EACH(j, adj[u]) {
      |     ^~~~
factories.cpp: In function 'int fct(int, int, int)':
factories.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
factories.cpp:75:5: note: in expansion of macro 'EACH'
   75 |     EACH(j, adj[u]) {
      |     ^~~~
factories.cpp: In function 'void centroid(int, int)':
factories.cpp:28:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   28 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
factories.cpp:87:5: note: in expansion of macro 'EACH'
   87 |     EACH(j, adj[ct]) {
      |     ^~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:95:5: note: in expansion of macro 'FOR'
   95 |     FOR(i, 0, N - 2) {
      |     ^~~
factories.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
factories.cpp:101:5: note: in expansion of macro 'FOS'
  101 |     FOS(i, cnt, 1) tin[a[i][0]] = i;
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:102:5: note: in expansion of macro 'FOR'
  102 |     FOR(j, 1, 19)
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:103:5: note: in expansion of macro 'FOR'
  103 |     FOR(i, 1, cnt) {
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:109:5: note: in expansion of macro 'FOR'
  109 |     FOR(i, 1, Nx2 - 1) LOG[i] = log2(i);
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:111:5: note: in expansion of macro 'FOR'
  111 |     FOR(i, 1, n) f[i] = oo;
      |     ^~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:114:5: note: in expansion of macro 'FOR'
  114 |     FOR(i, 0, S - 1) {
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:122:5: note: in expansion of macro 'FOR'
  122 |     FOR(i, 0, T - 1) {
      |     ^~~
factories.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
factories.cpp:129:5: note: in expansion of macro 'FOR'
  129 |     FOR(i, 0, S - 1) {
      |     ^~~

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