Submission #236262

#	Time	Username	Problem	Language	Result	Execution time	Memory
236262		DS007	Factories (JOI14_factories)	C++14	0 / 100	27 ms	24576 KiB

factories

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
 
const int N = 5e5;
vector<pair<int, long long>> adj[N];
int n, m;
 
/*int first[N], last[N], l2[N * 2], p2[N * 2];
long long dep[N];
int sparse[N * 2][22];
int c = 0;*/
 
int sub[N], par[N];
long long ans[N];
bool isCen[N];
int size = 0;
 
int block_size, block_cnt;
vector<int> first_visit;
vector<int> euler_tour;
vector<int> height;
vector<int> log_2;
vector<vector<int>> st;
vector<vector<vector<int>>> blocks;
vector<int> block_mask;
long long dep[N];
 
void dfs(int v, int p, int h, long long de = 0) {
    first_visit[v] = euler_tour.size();
    euler_tour.push_back(v);
    height[v] = h;
    dep[v] = de;
 
    for (auto u : adj[v]) {
        if (u.first == p)
            continue;
        dfs(u.first, v, h + 1, de + u.second);
        euler_tour.push_back(v);
    }
}
 
int min_by_h(int i, int j) {
    return height[euler_tour[i]] < height[euler_tour[j]] ? i : j;
}
 
void precompute_lca(int root) {
    // get euler tour & indices of first occurences
    first_visit.assign(n, -1);
    height.assign(n, 0);
    euler_tour.reserve(2 * n);
    dfs(root, -1, 0);
 
    // precompute all log values
    int m = euler_tour.size();
    log_2.reserve(m + 1);
    log_2.push_back(-1);
    for (int i = 1; i <= m; i++)
        log_2.push_back(log_2[i / 2] + 1);
 
    block_size = max(1, log_2[m] / 2);
    block_cnt = (m + block_size - 1) / block_size;
 
    // precompute minimum of each block and build sparse table
    st.assign(block_cnt, vector<int>(log_2[block_cnt] + 1));
    for (int i = 0, j = 0, b = 0; i < m; i++, j++) {
        if (j == block_size)
            j = 0, b++;
        if (j == 0 || min_by_h(i, st[b][0]) == i)
            st[b][0] = i;
    }
    for (int l = 1; l <= log_2[block_cnt]; l++) {
        for (int i = 0; i < block_cnt; i++) {
            int ni = i + (1 << (l - 1));
            if (ni >= block_cnt)
                st[i][l] = st[i][l-1];
            else
                st[i][l] = min_by_h(st[i][l-1], st[ni][l-1]);
        }
    }
 
    // precompute mask for each block
    block_mask.assign(block_cnt, 0);
    for (int i = 0, j = 0, b = 0; i < m; i++, j++) {
        if (j == block_size)
            j = 0, b++;
        if (j > 0 && (i >= m || min_by_h(i - 1, i) == i - 1))
            block_mask[b] += 1 << (j - 1);
    }
 
    // precompute RMQ for each unique block
    int possibilities = 1 << (block_size - 1);
    blocks.resize(possibilities);
    for (int b = 0; b < block_cnt; b++) {
        int mask = block_mask[b];
        if (!blocks[mask].empty())
            continue;
        blocks[mask].assign(block_size, vector<int>(block_size));
        for (int l = 0; l < block_size; l++) {
            blocks[mask][l][l] = l;
            for (int r = l + 1; r < block_size; r++) {
                blocks[mask][l][r] = blocks[mask][l][r - 1];
                if (b * block_size + r < m)
                    blocks[mask][l][r] = min_by_h(b * block_size + blocks[mask][l][r],
                                                  b * block_size + r) - b * block_size;
            }
        }
    }
}
 
int lca_in_block(int b, int l, int r) {
    return blocks[block_mask[b]][l][r] + b * block_size;
}
 
int lca(int v, int u) {
    int l = first_visit[v];
    int r = first_visit[u];
    if (l > r)
        swap(l, r);
    int bl = l / block_size;
    int br = r / block_size;
    if (bl == br)
        return euler_tour[lca_in_block(bl, l % block_size, r % block_size)];
    int ans1 = lca_in_block(bl, l % block_size, block_size - 1);
    int ans2 = lca_in_block(br, 0, r % block_size);
    int ans = min_by_h(ans1, ans2);
    if (bl + 1 < br) {
        int l = log_2[br - bl - 1];
        int ans3 = st[bl+1][l];
        int ans4 = st[br - (1 << l)][l];
        ans = min_by_h(ans, min_by_h(ans3, ans4));
    }
    return euler_tour[ans];
}
 
// LCA begins
/*void pre(int v, int p = -1, long long d = 0, int de = 0) {
    first[v] = c++;
    dep[v] = d;
    euler[c - 1] = v;
    depth[c - 1] = de;
 
    for (auto i : adj[v]) {
        if (i.first != p) {
            pre(i.first, v, d + i.second, de + 1);
            euler[c] = v;
            depth[c++] = de;
        }
    }
 
    last[v] = c - 1;
}
 
int merge(int a, int b) {
    return depth[a] < depth[b] ? a : b;
}
 
void build_sparse() {
    int es = n * 2 - 1;
    assert(es < N * 2);
    assert(l2[es] <= 22);
    for (int i = 0; i < es; i++)
        sparse[i][0] = i;
 
    for (int i = 1; i <= l2[es]; i++) {
        for (int j = 0; j < es && j - 1 + (p2[i]) < es; j++)
            sparse[j][i] = depth[sparse[j][i - 1]] < depth[sparse[j + (p2[i - 1])][i - 1]] ? sparse[j][i - 1] : sparse[j + (p2[i - 1])][i - 1];
    }
}
 
int lca(int u, int v) {
    if (u == v) return u;
    int f1 = min(first[u], first[v]), f2 = max(first[v], first[u]), diff = f2 - f1;
    int dx = l2[diff];
    return euler[merge(sparse[f1][dx], sparse[f2 - (p2[dx])][dx])];
}*/
 
 
long long dist(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
// LCA ends
 
// Centroid decomposition begins
void calc(int v, int p = -1) { // Pre calculate subtree sizes
    sub[v] = 1;
    size++;
    for (auto i : adj[v]) {
        if (i.first != p && !isCen[v])
            calc(i.first, v), sub[v] += sub[i.first];
    }
}
 
int find(int v, int p = -1) { // Find the centroid in current subtree
    for (auto i : adj[v]) {
        if (i.first != p && !isCen[i.first] && sub[i.first] > size / 2)
            return find(i.first, v);
    }
    return v;
}
 
void decompose(int v, int p = -1) {
    size = 0; // Stores size of current subtree
    calc(v);
    int centroid = find(v);
    par[centroid] = p;
    isCen[centroid] = true;
 
    for (auto i : adj[centroid]) {
        if (i.first != p && !isCen[i.first])
            decompose(i.first, centroid);
    }
}
// Centroid decomposition ends
 
void update(int v) {
    int p = v, co = 0;
    while (p != -1) {
        ans[p] = min(ans[p], dist(p, v));
        p = par[p];
    }
    assert(co <= 22);
}
 
long long query(int v) {
    int p = v, co = 0;
    long long val = 1e18;
    while (p != -1) {
        val = min(val, ans[p] + dist(p, v));
        p = par[p];
    }
    assert(co <= 22);
    return val;
}
 
void revert(int v) {
    int p = v;
    while (p != -1) {
        ans[p] = 1e18;
        p = par[p];
    }
}
 
 int qc = 0;
long long Query(int S, int X[], int T, int Y[]) {
    if (S <= 10 && T <= 10) {
        long long ans = 1e18;
        for (int i = 0; i < S; i++) {
            for (int j = 0; j < T; j++)
                ans = min(ans, dep[X[i]] + dep[Y[j]] - 2 * dep[lca(X[i], Y[j])]);
        }
        qc++;
    	assert(n == N && qc <= 80000);
        return ans;
    } else exit(0);
 
    for (int i = 0; i < S; i++)
        update(X[i]);
    long long ans = 1e18;
    for (int i = 0; i < T; i++)
        ans = min(ans, query(Y[i]));
    for (int i = 0; i < S; i++)
        revert(X[i]);
    return ans;
}
 
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
 
    precompute_lca(0);
    decompose(0);
    fill(ans, ans + N, 1e18);
}

Compilation message (stderr)

factories.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
factories.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

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