Submission #914363

#	Time	Username	Problem	Language	Result	Execution time	Memory
914363		DorostWef	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	2007 ms	38024 KiB

reconstruction

/*  In the name of GOD */

#include <bits/stdc++.h>

using namespace std;
#define F first
#define S second
#define mk make_pair 
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
const int N = 505, M = 100034, INF = 2000 * 1000 * 1005;
int p[N], sz[N];
ll ans[M * 10];

void reset () {
    for (int i = 0; i < N; i++) {
        p[i] = i;
        sz[i] = 1;
    }
}

int get_par (int v) {
    return (p[v] == v ? v : p[v] = get_par(p[v]));
}

void merge (int u, int v) {
    u = get_par(u);
    v = get_par(v);
    if (u == v)
        return;
    if (sz[u] > sz[v])
        swap (u, v);
    p[u] = v;
    sz[v] += sz[u];
}

struct Edge {
    int u, v, w;
    bool operator< (Edge B) {
        return w < B.w;
    }
} a[M];

int32_t main () {
    ios::sync_with_stdio(false);
    cin.tie();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i].u >> a[i].v >> a[i].w;
    sort (a + 1, a + m + 1);
    vector <int> wef;
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        wef.push_back(x);
    }
    for (int i = 1; i <= m; i++) {
        a[0].u = a[i].u;
        a[0].v = a[i].v;
        a[0].w = -INF;
        a[m + 1] = a[0];
        a[m + 1].w = INF;
        ll x = -1;
        reset ();
        for (int j = i - 1; j >= 0; j--) {
            merge (a[j].u, a[j].v);
            if (get_par(a[0].u) == get_par(a[0].v)) {
                x = a[j].w;
                break;
            }
        }
        int l = (x + a[i].w + 1) / 2;
        reset ();
        for (int j = i + 1; j <= m + 1; j++) {
            merge (a[j].u, a[j].v);
            if (get_par(a[0].u) == get_par(a[0].v)) {
                x = a[j].w;
                break;
            }
        }
        int r = (x + a[i].w - 1) / 2;
        int in = lower_bound (wef.begin(), wef.end(), l) - wef.begin();
        for (; in < q && wef[in] <= r; in++) {
            ans[in] += abs(wef[in] - a[i].w);
        }
    }
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

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