Submission #1198127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198127		LucaIlie	Reconstruction Project (JOI22_reconstruction)	C++20	31 / 100	3607 ms	409552 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v, w;
};

struct DSU {
    vector<int> parent;

    void init(int n) {
        parent.clear();
        parent.resize(n + 1);
        for (int i = 0; i <= n; i++)
            parent[i] = i;
    }

    int findParent(int v) {
        if (parent[v] != v)
            parent[v] = findParent(parent[v]);
        return parent[v];
    }

    void connect(int u, int v) {
        u = findParent(u);
        v = findParent(v);
        if (u == v)
            return;
        parent[v] = u;
    }

    bool connected(int u, int v) {
        u = findParent(u);
        v = findParent(v);
        return (u == v);
    }
};

struct event {
    int t, x, c;
};

struct query {
    int w, i;
    long long ans;
};

const int MAX_M = 1e5;
const int MAX_Q = 1e6;
const int INF = 1e9 + 6;
vector<int> lowerEdges[MAX_M + 1], higherEdges[MAX_M + 2];
vector<event> events;
edge edges[MAX_M + 1];
query queries[MAX_Q];
DSU dsu;

void addInterval(int l, int r, int x, int c) {
    /* printf("Interval %d %d %d %d\n", l, r, x, c); */
    if (l > r)
        return;
    x *= c;
    events.push_back({l, x, c});
    events.push_back({r + 1, -x, -c});
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;

    cin >> n >> m;
    for (int e = 1; e <= m; e++)
        cin >> edges[e].u >> edges[e].v >> edges[e].w;
    edges[0].w = 0;
    edges[m + 1].w = INF;

    sort(edges + 1, edges + 1 + m, [](edge a, edge b) {
        return a.w < b.w;
    });

    for (int e = 1; e <= m; e++) {
        dsu.init(n);
        dsu.connect(edges[e].u, edges[e].v);
        lowerEdges[e].push_back(e);
        for (int f: lowerEdges[e - 1]) {
            if (!dsu.connected(edges[f].u, edges[f].v)) {
                dsu.connect(edges[f].u, edges[f].v);
                lowerEdges[e].push_back(f);
            }
        }
    }

    for (int e = m; e >= 1; e--) {
        dsu.init(n);
        dsu.connect(edges[e].u, edges[e].v);
        higherEdges[e].push_back(e);
        for (int f: higherEdges[e + 1]) {
            if (!dsu.connected(edges[f].u, edges[f].v)) {
                dsu.connect(edges[f].u, edges[f].v);
                higherEdges[e].push_back(f);
            }
        }
    }

    for (int t = 0; t <= m; t++) {
        /* printf("\n\n\nWW %d %d\n", t, edges[t].w); */
        /* printf("LOWER\n"); */
        /* for (int e: lowerEdges[t]) */
        /*     printf("%d %d %d\n", edges[e].u, edges[e].v, edges[e].w); */
        /* printf("HIGHER\n"); */
        /* for (int e: higherEdges[t + 1]) */
        /*     printf("%d %d %d\n", edges[e].u, edges[e].v, edges[e].w); */
        /* printf("\n"); */

        for (int i = 0; i < (int)lowerEdges[t].size(); i++) {
            dsu.init(n);
            int e = lowerEdges[t][i];
            for (int j = 0; j < i; j++) {
                int f = lowerEdges[t][j];
                dsu.connect(edges[f].u, edges[f].v);
            }
            int j = -1;
            while (j + 1 < (int)higherEdges[t + 1].size() && !dsu.connected(edges[e].u, edges[e].v)) {
                j++;
                int f = higherEdges[t + 1][j];
                dsu.connect(edges[f].u, edges[f].v);
            }

            if (!dsu.connected(edges[e].u, edges[e].v))
                addInterval(edges[t].w, edges[t + 1].w - 1, edges[e].w, -1);
            else {
                int f = higherEdges[t + 1][j];
                int a = edges[e].w, b = edges[f].w;
                addInterval(edges[t].w, min(edges[t + 1].w - 1, (a + b) / 2), edges[e].w, -1);
            }
        }
        for (int i = 0; i < (int)higherEdges[t + 1].size(); i++) {
            dsu.init(n);
            int e = higherEdges[t + 1][i];
            for (int j = 0; j < i; j++) {
                int f = higherEdges[t + 1][j];
                dsu.connect(edges[f].u, edges[f].v);
            }
            int j = -1;
            while (j + 1 < (int)lowerEdges[t].size() && !dsu.connected(edges[e].u, edges[e].v)) {
                j++;
                int f = lowerEdges[t][j];
                dsu.connect(edges[f].u, edges[f].v);
            }

            if (!dsu.connected(edges[e].u, edges[e].v))
                addInterval(edges[t].w, edges[t + 1].w - 1, edges[e].w, +1);
            else {
                int f = lowerEdges[t][j];
                int a = edges[e].w, b = edges[f].w;
                addInterval(max(edges[t].w, (a + b) / 2 + 1), edges[t + 1].w - 1, edges[e].w, +1);
            }
        }
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> queries[i].w;
        queries[i].i = i;
    }

    sort(queries, queries + q, [](query a, query b) {
        return a.w < b.w;
    });
    sort(events.begin(), events.end(), [](event a, event b) {
        return a.t < b.t;
    });

    int j = 0;
    long long cost = 0, cnt = 0;
    for (int i = 0; i < q; i++) {
        while (j < (int)events.size() && events[j].t <= queries[i].w) {
            cost += events[j].x;
            cnt += events[j].c;
            j++;
        }
        queries[i].ans = cost - (long long)queries[i].w * cnt;
    }

    sort(queries, queries + q, [](query a, query b) {
        return a.i < b.i;
    });

    for (int i = 0; i < q; i++)
        cout << queries[i].ans << "\n";

    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 28 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23