Submission #1282108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282108		baotoan655	Factories (JOI14_factories)	C++20	100 / 100	3243 ms	321148 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const long long INF = 1e16;
const int N = 5e5 + 5;
int n, q;
vector<pair<int, int>> g[N];
vector<pair<int, long long>> fa[N];
long long bst[N];
bool del[N];
int sz[N];

void get_sz(int u, int p) {
    sz[u] = 1;
    for(auto it : g[u]) if(it.first != p && !del[it.first]) {
        get_sz(it.first, u);
        sz[u] += sz[it.first];
    }
}
int get_cen(int u, int p, int tt) {
    for(auto it : g[u]) if(it.first != p && !del[it.first]) {
        if(sz[it.first] * 2 > tt) return get_cen(it.first, u, tt);
    }
    return u;
}
void dfs(int u, int p, int cen, long long d) {
    fa[u].emplace_back(cen, d);
    for(auto it : g[u]) if(!del[it.first] && it.first != p) {
        dfs(it.first, u, cen, d + it.second);
    }
}
void centroid(int u) {
    get_sz(u, -1);
    int cen = get_cen(u, -1, sz[u]);
    del[cen] = true;
    for(auto it : g[cen]) if(!del[it.first]) {
        dfs(it.first, cen, cen, it.second);
    }
    for(auto it : g[cen]) if(!del[it.first]) centroid(it.first);
}

void Init(int _n, int A[], int B[], int D[]) {
    memset(bst, 0x3f, sizeof bst);
    n = _n;
    for(int i = 0; i < n - 1; ++i) {
        g[A[i]].emplace_back(B[i], D[i]);
        g[B[i]].emplace_back(A[i], D[i]);
    }
    centroid(0);
//    for(int i = 0; i < n; ++i) {
//        for(auto [j, w] : fa[i]) cout << i << ' ' << j << ' ' << w << '\n';
//    }
}
void upd(int u) {
    bst[u] = 0;
    for(auto it : fa[u]) bst[it.first] = min(bst[it.first], it.second);
}
long long get(int u) {
    long long res = bst[u];
    for(auto it : fa[u]) res = min(res, bst[it.first] + it.second);
    return res;
}
void unupd(int u) {
    bst[u] = INF;
    for(auto it : fa[u]) bst[it.first] = INF;
}
long long Query(int S, int X[], int T, int Y[]) {
    for(int i = 0; i < S; ++i) upd(X[i]);
    long long res = INF;
    for(int i = 0; i < T; ++i) res = min(res, get(Y[i]));
    for(int i = 0; i < S; ++i) unupd(X[i]);
    return res;
}

//int main() {
//    ios_base::sync_with_stdio(false);
//    cin.tie(0), cout.tie(0);
//
//    file("A") else file("task");
//    int _n, _q;
//    cin >> _n >> _q;
//    int A[_n], B[_n], D[_n];
//    for(int i = 0; i < _n - 1; ++i) {
//        cin >> A[i] >> B[i] >> D[i];
//    }
//    Init(_n, A, B, D);
//    while(_q--) {
//        int S, T;
//        cin >> S >> T;
//        int X[S], Y[T];
//        for(int i = 0; i < S; ++i) cin >> X[i];
//        for(int i = 0; i < T; ++i) cin >> Y[i];
//        cout << Query(S, X, T, Y) << '\n';
//    }
//    return 0;
//}
//

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