oj.uz

답안 #422643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
422643 2021-06-10T09:31:40 Z tengiz05 공장들 (JOI14_factories) C++17
0 / 100
 8000 ms 370068 KB 
#pragma GCC optimize("O3,Ofast")
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 21, M = 2 * N + 1;
std::vector<std::pair<int, int>> e[N];
i64 st[K + 1][M];
int lg[M + 1], n, P[N], timer;
i64 D[N];
i64 pos[M];
int order[N], timeStamp;
int par[N];
int dpar[N];
void dfs(int u, int p, i64 d = 0){
    order[timeStamp++] = u;
    par[u] = p;
    P[u] = timer;
    pos[timer++] = d;
    D[u] = d;
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dpar[v] = w;
            dfs(v, u, d + w);
            pos[timer++] = d;
        }
    }
}
inline i64 dist(int u, int v) {
    int L = P[u], R = P[v];
    if (L > R) std::swap(L, R);
    int j = lg[R - L + 1];
    return D[u] + D[v] - std::min(st[j][L], st[j][R - (1 << j) + 1]);
}
bool vis[N];
int siz[N], now;
std::vector<int> have;
void calc_s(int u, int p) {
    have.push_back(u);
    siz[u] = 1;
    for (auto [v, w] : e[u]) {
        if (!vis[v] && v != p) {
            calc_s(v, u);
            siz[u] += siz[v];
        }
    }
}
int centroid(int u, int p) {
    for (auto [v, w] : e[u]) {
        if (!vis[v] && v != p && siz[u] > now / 2) {
            return centroid(v, u);
        }
    }
    return u;
}
std::vector<int> cpar[N];
void decompose(int u) {
    have.clear();
    calc_s(u, u);
    now = siz[u];
    u = centroid(u, u);
    vis[u] = true;
    for (auto x : have) {
        cpar[x].push_back(u);
    }
    for (auto [v, w] : e[u]) {
        if (!vis[v]) {
            decompose(u);
        }
    } 
}
i64 dp[N];
i64 res[N];
void Init(int n, int A[], int B[], int D[]) {
    memset(res, 0x3f, sizeof res);
    lg[1] = 0;
    for (int i = 2; i <= M; i++)
        lg[i] = lg[i / 2] + 1;
    ::n = n;
    for (int i = 0; i < n - 1; i++) {
        e[A[i]].emplace_back(B[i], D[i]);
        e[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(0, 0);
    for (int i = 0; i < M; i++)
        st[0][i] = 2 * pos[i];
    for (int j = 1; j <= K; j++)
        for (int i = 0; i + (1 << j) <= M; i++)
            st[j][i] = std::min(st[j-1][i], st[j - 1][i + (1 << (j - 1))]);
    // std::cerr << "fu";
    decompose(0);
    // std::cerr << "ck\n";
}
i64 Query(int S, int X[], int T, int Y[]) {
    if (S + T <= 56050) {
        std::vector<int> changed;
        for (int i = 0; i < S; i++) {
            int u = X[i];
            for (auto v : cpar[u]) {
                changed.push_back(v);
                res[v] = std::min(res[v], dist(u, v));
            }
        }
        i64 ans = 1e17;
        for (int i = 0; i < T; i++) {
            int u = Y[i];
            for (auto v : cpar[u]) {
                ans = std::min(ans, res[v] + dist(u, v));
            }
        }
        for (auto x : changed) {
            res[x] = 1e17;
        }
        return ans;
    }
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i < S; i++) {
        dp[X[i]] = 0;
    }
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        dp[par[u]] = std::min(dp[par[u]], dp[u] + dpar[u]);
    }
    for (int i = 0; i < n; i++) {
        int u = order[i];
        dp[u] = std::min(dp[u], dp[par[u]] + dpar[u]);
    }
    i64 ans =  1e16;
    for (int i = 0; i < T; i++) {
        ans = std::min(ans, dp[Y[i]]);
    }
    return ans;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 180476 KB Output is correct
2 Correct 1909 ms 191144 KB Output is correct
3 Correct 4107 ms 193564 KB Output is correct
4 Correct 4037 ms 199264 KB Output is correct
5 Correct 1040 ms 189972 KB Output is correct
6 Execution timed out 8074 ms 287688 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 180284 KB Output is correct
2 Execution timed out 8103 ms 370068 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 180476 KB Output is correct
2 Correct 1909 ms 191144 KB Output is correct
3 Correct 4107 ms 193564 KB Output is correct
4 Correct 4037 ms 199264 KB Output is correct
5 Correct 1040 ms 189972 KB Output is correct
6 Execution timed out 8074 ms 287688 KB Time limit exceeded
7 Halted 0 ms 0 KB -