oj.uz

Submission #914356

# Submission time Handle Problem Language Result Execution time Memory
914356 2024-01-21T18:06:38 Z DorostWef Reconstruction Project (JOI22_reconstruction) C++14
0 / 100
 848 ms 1048576 KB 
/*  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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Runtime error 5 ms 8796 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Runtime error 5 ms 8796 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Runtime error 848 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Runtime error 5 ms 8796 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Runtime error 5 ms 8796 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Runtime error 5 ms 8796 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -