Submission #914356

#	Time	Username	Problem	Language	Result	Execution time	Memory
914356		DorostWef	Reconstruction Project (JOI22_reconstruction)	C++14	0 / 100	848 ms	1048576 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;
#define int long long
const int N = 505, M = 100034, INF = 2000 * 1000 * 1005;
int p[N], sz[N];
ll ans[M * 10], cnt[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 = p[u];
    v = p[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++) {
            cnt[in]++;
            ans[in] += abs(wef[in] - a[i].w);
        }
    }   
    for (int i = 0; i < q; i++) {
        assert (cnt[i] == n - 1); 
        cout << ans[i] << '\n';
    }   
}

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