Submission #1036865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036865		TrendBattles	Factories (JOI14_factories)	C++14	100 / 100	3324 ms	194232 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using lli = long long;

const int MAX_N = 1 << 19;
vector <int> graph[MAX_N];
struct Edge {
    int u, v, w;
    Edge(int _u = 0, int _v = 0, int _w = 0):
        u(_u), v(_v), w(_w) {}

    int get_other(int x) const {
        return x ^ u ^ v;
    }
};
Edge edge[MAX_N];


lli pref_w[MAX_N];
int in[MAX_N], depth[MAX_N];
int timeDFS = 0;
int mn_depth[__lg(MAX_N) + 1][MAX_N << 1];
void DFS(int u) {
    in[u] = ++timeDFS;

    mn_depth[0][in[u]] = u;
    for (int id : graph[u]) {
        int v = edge[id].get_other(u);
        if (in[v]) continue;

        depth[v] = depth[u] + 1;
        pref_w[v] = pref_w[u] + edge[id].w;
        DFS(v);

        mn_depth[0][++timeDFS] = u;
    }
}

int Find_LCA(int u, int v) {
    if (in[u] > in[v]) swap(u, v);
    int k = __lg(in[v] - in[u] + 1);

    int& x = mn_depth[k][in[u]]; int& y = mn_depth[k][in[v] - (1 << k) + 1];
    return depth[x] < depth[y] ? x : y;
}
lli Path_Len(int u, int v) {
    return pref_w[u] + pref_w[v] - 2 * pref_w[Find_LCA(u, v)];
}

int removed[MAX_N], cen_parent[MAX_N], sub_sz[MAX_N];

int Find_Centroid(int s, int sz) {
    int last = s, parent = 0;
    while (true) {
        for (int id : graph[s]) {
            int v = edge[id].get_other(s);
            if (v == parent or removed[v]) continue;

            if (sub_sz[v] * 2 > sz) {
                last = v; break;
            }
        }
        if (last == s) break;
        parent = s; s = last;
    }
    return last;
}
int get_size(int u, int parent) {
    sub_sz[u] = 1;
    for (int id : graph[u]) {
        int v = edge[id].get_other(u);
        if (v == parent or removed[v]) continue;
        
        sub_sz[u] += get_size(v, u);
    }
    return sub_sz[u];
}
int Build_Centroid(int s) {
    int cen_node = Find_Centroid(s, get_size(s, 0));
    removed[cen_node] = true;

    for (int id : graph[cen_node]) {
        int v = edge[id].get_other(cen_node);
        if (removed[v]) continue;

        int x = Build_Centroid(v);
        cen_parent[x] = cen_node;
    }   

    return cen_node;
}

lli min_path[MAX_N];
const lli inf = 0x3f3f3f3f3f3f3f3f;
void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; ++i) {
        A[i] += 1; B[i] += 1;
        edge[i] = Edge(A[i], B[i], D[i]);

        graph[A[i]].push_back(i);
        graph[B[i]].push_back(i);
    }

    DFS(1);
    for (int i = 1; i <= __lg(N) + 1; ++i) {
        for (int u = 1; u + (1 << i) <= timeDFS + 1; ++u) {
            int& x = mn_depth[i - 1][u]; int& y = mn_depth[i - 1][u + (1 << (i - 1))];
            mn_depth[i][u] = depth[x] < depth[y] ? x : y;
        }
    }
    
    Build_Centroid(1);

    memset(min_path, 0x3f, sizeof min_path);
}

void minimise(lli& x, lli y) {
    if (x > y) x = y;
}
void Update(int pos) {
    int c = pos;
    while (c) {
        minimise(min_path[c], Path_Len(c, pos));
        c = cen_parent[c];
    }
}

lli Ask(int pos) {
    lli ans = inf;

    int c = pos;
    while (c) {
        minimise(ans, min_path[c] + Path_Len(c, pos));
        c = cen_parent[c];
    }
    return ans;
}
void Clean(int pos) {
    int c = pos;
    while (c) {
        min_path[c] = inf;
        c = cen_parent[c];
    }
}
lli Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++i) {
        X[i] += 1;
        Update(X[i]);
    }

    lli mn = inf;
    for (int i = 0; i < T; ++i) {
        Y[i] += 1;
        minimise(mn, Ask(Y[i]));
    }

    for (int i = 0; i < S; ++i) {
        Clean(X[i]);
    }
    return mn;
}

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