Submission #1198189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198189		LucaIlie	Reconstruction Project (JOI22_reconstruction)	C++20	0 / 100	23 ms	6456 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 = -INF;
    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++) {
        int f = e;
        dsu.init(n);
        while (f + 1 <= m + 1 && !dsu.connected(edges[e].u, edges[e].v)) {
            f++;
            dsu.connect(edges[f].u, edges[f].v);
        }
        int a = edges[e].w, b = edges[f].w;
        addInterval(edges[e].w, (a + b) / 2, edges[e].w, -1);
    }
    for (int e = m; e >= 1; e--) {
        int f = e;
        dsu.init(n);
        while (f - 1 >= 0 && !dsu.connected(edges[e].u, edges[e].v)) {
            f--;
            dsu.connect(edges[f].u, edges[f].v);
        }
        int a = edges[e].w, b = edges[f].w;
        addInterval((a + b) / 2 + 1, edges[e].w, 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: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23