Submission #1136829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136829		onbert	공장들 (JOI14_factories)	C++20	100 / 100	2662 ms	342724 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5, INF = 1e18;
int n;
vector<pair<int,int>> adj[maxn];


vector<pair<int,int>> vec[maxn];

int cent = -1, sz;
int dfs(int u, int p) {
    int usz = 1;
    bool can = true;
    for (auto [v, w]:adj[u]) if (v != p) {
        int cur = dfs(v, u);
        if (cur > sz / 2) can = false;
        usz += cur;
    }
    // cout << u << " " << usz << " " << can << endl;
    if (can && sz - usz <= sz / 2) cent = u;
    return usz;
}

void dfs2(int u, int dist, int p) {
    vec[u].push_back({cent, dist});
    for (auto [v, w]:adj[u]) if (v != p) dfs2(v, dist + w, u);
}

vector<int> nodes;
void dfs3(int u, int p) {
    nodes.push_back(u);
    // cout << "dfs3 " << u << endl;
    for (auto [v, w]:adj[u]) if (v != p) {
        // cout << u << " " << v << endl;
        dfs3(v, u);
    }
}

void decomp(int u) {
    sz = nodes.size(), cent = u;
    dfs(u, -1);
    // cout << u << " " << sz << " " << cent << endl;
    // for (int i:nodes) cout << i << " "; cout << endl;
    int curcent = cent;
    dfs2(cent, 0, -1);
    for (auto [v, w]:adj[curcent]) {
        adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(curcent, w)));
        nodes.clear();
        // cout << u << " " << v << endl;
        dfs3(v, -1);
        decomp(v);
    }
}

int mn[maxn];
void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
    n = N;
    for (int i=0;i<n-1;i++) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    for (int i=0;i<n;i++) nodes.push_back(i);
    decomp(0);
    // cout << "test\n";
    for (int i=0;i<n;i++) mn[i] = INF;
}

int Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
    for (int i=0;i<S;i++) {
        for (auto [c, val]:vec[X[i]]) mn[c] = min(val, mn[c]);
    }
    int ans = INF;
    for (int i=0;i<T;i++) {
        for (auto [c, val]:vec[Y[i]]) ans = min(val + mn[c], ans);
    }
    for (int i=0;i<S;i++) {
        for (auto [c, val]:vec[X[i]]) mn[c] = INF;
    }
    return ans;
}

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