Submission #48390

#	Time	Username	Problem	Language	Result	Execution time	Memory
48390		maksim_gaponov	Factories (JOI14_factories)	C++14	15 / 100	6101 ms	241628 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;
typedef long long ll;
/*
void openFiles() {
#ifdef KEK
	assert(freopen("input.txt", "r", stdin));
	assert(freopen("output.txt", "w", stdout));
#endif
}
*/
void IOoptimize() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int MAXN = 5e5 + 10;
const int MAXLOG = 20;
const ll INF = 1e17;
vector<pair<int, ll>> g[MAXN];
int n;
int type[MAXN];
ll dist[MAXN];
int jump[MAXLOG][MAXN];
ll sum[MAXLOG][MAXN];
bool second_group;
bool used[MAXN];
int h[MAXN];

void dfs(int u, int height) {
    used[u] = true;
    h[u] = height;
    for (auto v : g[u]) {
        if (!used[v.first]) {
            jump[0][v.first] = u;
            sum[0][v.first] = v.second;
            dfs(v.first, height + 1);
        }
    }
}

bool get_bit(int mask, int i) {
    return (mask & (1 << i));
}

ll get_dist(int x, int y) {
    ll res = 0;
    if (h[x] < h[y])
        swap(x, y);
    int diff = h[x] - h[y];
    for (int i = 0; i < MAXLOG; i++) {
        if (get_bit(diff, i)) {
            res += sum[i][x];
            x = jump[i][x];
        }
    }
    if (x != y) {
        for (int i = MAXLOG - 1; i >= 0; i--) {
            if (jump[i][x] != jump[i][y]) {
                res += sum[i][x];
                res += sum[i][y];
                x = jump[i][x];
                y = jump[i][y];
            }
        }
        res += sum[0][x];
        res += sum[0][y];
    }
    return res;
}

void Init(int N, int A[], int B[], int D[]) {
    IOoptimize();
    n = N;
    for (int i = 0; i < n - 1; i++) {
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    second_group = (n > 5000);
    if (second_group) {
        dfs(0, 0);
        for (int k = 1; k < MAXLOG; k++) {
            for (int i = 0; i < n; i++) {
                jump[k][i] = jump[k - 1][jump[k - 1][i]];
                sum[k][i] = sum[k - 1][i] + sum[k - 1][jump[k - 1][i]];
            }
        }
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    if (second_group) {
        ll ans = INF;
        for (int i = 0; i < S; i++) {
            for (int j = 0; j < T; j++) {
                ans = min(ans, get_dist(X[i], Y[j]));
            }
        }
        return ans;
    }
    else {
        memset(type, 0, sizeof(type));
        for (int i = 0; i < T; i++) {
            type[Y[i]] = 1;
        }
        for (int i = 0; i < n; i++) {
            dist[i] = INF;
        }
        priority_queue<pair<ll, int>> q;
        for (int i = 0; i < S; i++) {
            dist[X[i]] = 0;
            q.push({-dist[X[i]], X[i]});
        }
        while (!q.empty()) {
            ll cur_dist = -q.top().first;
            int cur = q.top().second;
            q.pop();
            if (cur_dist != dist[cur])
                continue;
            if (type[cur] == 1) {
                return dist[cur];
            }
            for (auto v : g[cur]) {
                if (dist[v.first] > dist[cur] + v.second) {
                    dist[v.first] = dist[cur] + v.second;
                    q.push({-dist[v.first], v.first});
                }
            }
        }
    }
    return INF;
}

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