제출 #713598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713598		Spade1	공장들 (JOI14_factories)	C++14	15 / 100	8026 ms	439776 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
//#include "grader.cpp"
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define pb push_back
#define INF 1e18
using namespace std;

const int maxN = 500050;
const int L = log2(maxN) + 10;

vector<pll> adj[maxN];
set<ll> s;
bool mark[maxN];
ll sz[maxN], mn[maxN], up[maxN], dist[maxN][L], lvl[maxN], P[maxN][L], updist[maxN][L];

void dfs2(int a, int prt, ll cur) {
    lvl[a] = lvl[prt]+1;
    P[a][0] = prt;
    updist[a][0] = cur;
    for (int i = 1; i < L; ++i) {
        P[a][i] = P[P[a][i-1]][i-1];
        updist[a][i] = updist[P[a][i-1]][i-1] + updist[a][i-1];
    }
    for (auto [b, w] : adj[a]) if (b != prt) dfs2(b, a, w);
}

long long lca(int a, int b) {
    if (lvl[a] < lvl[b]) swap(a, b);
    int j = lvl[a] - lvl[b];
    ll dis = 0;
    for (int i = 0; i < L; ++i) {
        if (j & (1<<i)) {
            dis += updist[a][i];
            a = P[a][i];
        }
    }
    if (a==b) return dis;
    for (int i = L-1; i >= 0; --i) {
        if (P[a][i] != P[b][i]) {
            dis += (updist[a][i] + updist[b][i]);
            a = P[a][i]; b = P[b][i];
        }
    }
    return dis + updist[a][0] + updist[b][0];
}

void computedist(int n) {
    for (int i = 0; i < n; ++i) {
        int cnt = 0;
        for (int j = i; j != -1; j = up[j]) {
            dist[i][cnt++] = lca(i, j);
        }
    }
}

int dfs(int i, int prt=-1) {
    sz[i] = 1;
    for (auto [j, w] : adj[i]) {
        if (j == prt || mark[j]) continue;
        sz[i] += dfs(j, i);
    }
    return sz[i];
}

int find_centroid(int i, int m, int prt=-1) {
    for (auto [j, w] : adj[i]) {
        if (j == prt || mark[j]) continue;
        if (sz[j] > m/2) return find_centroid(j, m, i);
    }
    return i;
}

int decom(int x=0) {
    int cen = find_centroid(x, dfs(x));
    mark[cen] = 1;

    for (auto [j, w] : adj[cen]) {
        if (mark[j]) continue;
        int c = decom(j);
        up[c] = cen;
    }
    return cen;
}

void update(int v) {
    int cur = v, cnt = 0;
    while (cur != -1) {
        s.insert(cur);
        mn[cur] = min(mn[cur], dist[v][cnt]);
        cur = up[cur];
        cnt++;
    }
}

ll query(int v) {
    ll ans = INF, cur = v, cnt = 0;
    while (cur != -1) {
        ans = min(ans, mn[cur] + dist[v][cnt]);
        cur = up[cur];
        cnt++;
    }
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; ++i) {
        adj[A[i]].pb({B[i], D[i]});
        adj[B[i]].pb({A[i], D[i]});
    }
    for (int i = 0; i < N; ++i) mn[i] = INF;
    memset(up, -1, sizeof(up));
    decom();
    dfs2(0, -1, 0);
    computedist(N);
}

ll Query(int S, int X[], int T, int Y[]) {
    s.clear();
    for (int i = 0; i < S; ++i) update(X[i]);
    ll ans = INF;
    for (int i = 0; i < T; ++i) ans = min(ans, query(Y[i]));
    for (auto i : s) mn[i] = INF;
    return ans;
}

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

factories.cpp: In function 'void dfs2(int, int, long long int)':
factories.cpp:29:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for (auto [b, w] : adj[a]) if (b != prt) dfs2(b, a, w);
      |               ^
factories.cpp: In function 'int dfs(int, int)':
factories.cpp:63:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:71:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'int decom(int)':
factories.cpp:82:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for (auto [j, w] : adj[cen]) {
      |               ^

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