Submission #1176621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176621		trufanov.p	Factories (JOI14_factories)	C++20	100 / 100	2553 ms	343380 KiB

factories

#include "factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;

const ll INF = 1e15;

vector<vector<pair<int, ll>>> gr;
vector<int> sz;
vector<bool> blocked;
vector<vector<pair<int, ll>>> anc;
vector<ll> mindist;
vector<int> last;
int timer = 0;

int dfs_size(int v, int p = -1) {
    sz[v] = 1;
    for (auto& [u, w] : gr[v]) {
        if (u != p && !blocked[u]) {
            sz[v] += dfs_size(u, v);
        }
    }
    return sz[v];
}

int find_centroid(int v, int total_size, int p = -1) {
    for (auto& [u, w] : gr[v]) {
        if (u != p && !blocked[u]) {
            if (sz[u] * 2 >= total_size) {
                return find_centroid(u, total_size, v);
            }
        }
    }
    return v;
}

void calc_dist(int v, int centr, ll d, int p = -1) {
    anc[v].push_back({ centr, d });
    for (auto& [u, w] : gr[v]) {
        if (u != p && !blocked[u]) {
            calc_dist(u, centr, d + w, v);
        }
    }
}

void build_decomposition(int v) {
    int centr = find_centroid(v, dfs_size(v));
    blocked[centr] = true;
    anc[centr].push_back({ centr, 0 });
    for (auto& [u, w] : gr[centr]) {
        if (!blocked[u]) {
            calc_dist(u, centr, w);
        }
    }
    for (auto& [u, w] : gr[centr]) {
        if (!blocked[u]) {
            build_decomposition(u);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    gr.resize(N);
    for (int i = 0; i < N - 1; ++i) {
        int u = A[i], v = B[i], d = D[i];
        gr[u].push_back({ v, d });
        gr[v].push_back({ u, d });
    }
    sz.resize(N);
    blocked.resize(N);
    anc.resize(N);
    mindist.resize(N, INF);
    last.resize(N, -1);
    build_decomposition(0);
}

void paint(int v, int timer) {
    for (auto& [p, d] : anc[v]) {
        if (last[p] != timer) {
            mindist[p] = d;
        } else {
            mindist[p] = min(mindist[p], d);
        }
        last[p] = timer;
    }
}

ll get_mindist(int v, int timer) {
    ll ans = INF;
    for (auto& [p, d] : anc[v]) {
        if (last[p] == timer) {
            ans = min(ans, d + mindist[p]);
        }
    }
    return ans;
}

ll Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++i) {
        paint(X[i], timer);
    }
    ll ans = INF;
    for (int i = 0; i < T; ++i) {
        ans = min(ans, get_mindist(Y[i], timer));
    }
    timer++;
    return ans;
}

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