oj.uz

Submission #959394

# Submission time Handle Problem Language Result Execution time Memory
959394 2024-04-08T06:51:17 Z alextodoran Reconstruction Project (JOI22_reconstruction) C++17
42 / 100
 5000 ms 539632 KB 
/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500;
const int M_MAX = 100000;
const int Q_MAX = 1000000;
const int INF = (int) 1e9 + 2;

int N, M, Q;
int edge_u[M_MAX + 2], edge_v[M_MAX + 2];
int edge_c[M_MAX + 2];

int order[M_MAX + 2];

int min_q[M_MAX + 2], max_q[M_MAX + 2];

int other (int i, int x) {
    return (x != edge_u[i] ? edge_u[i] : edge_v[i]);
}

vector <int> adj[N_MAX + 2];

vector <int> chain;
bool dfs (int u, int v, int last = 0) {
    if (u == v) {
        return true;
    }
    for (int i : adj[u]) {
        if (i != last) {
            if (dfs(other(i, u), v, i) == true) {
                chain.push_back(i);
                return true;
            }
        }
    }
    return false;
}
void add (int i) {
    int u = edge_u[i], v = edge_v[i];
    adj[u].push_back(i);
    adj[v].push_back(i);
}
void del (int i) {
    int u = edge_u[i], v = edge_v[i];
    adj[u].erase(find(adj[u].begin(), adj[u].end(), i));
    adj[v].erase(find(adj[v].begin(), adj[v].end(), i));
}

void update (unordered_map <int, ll> &Fen, int pos, int val) {
    for (int i = pos; i <= INF; i += i & -i) {
        Fen[i] += val;
    }
}
void update (unordered_map <int, ll> &Fen, int l, int r, int val) {
    if (l <= r) {
        update(Fen, l, val);
        update(Fen, r + 1, -val);
    }
}
ll query (unordered_map <int, ll> &Fen, int pos) {
    ll sum = 0;
    for (int i = pos; i >= 1; i -= i & -i) {
        sum += Fen[i];
    }
    return sum;
}

unordered_map <int, ll> Fen_sum_l, Fen_sum_r, Fen_cnt_l;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        cin >> edge_u[i] >> edge_v[i] >> edge_c[i];
    }
    iota(order + 1, order + M + 1, 1);
    sort(order + 1, order + M + 1, [&] (const int &i, const int &j) {
        return edge_c[i] < edge_c[j];
    });
    for (int k = 1; k <= M; k++) {
        int i = order[k]; int u = edge_u[i], v = edge_v[i];
        if (dfs(u, v) == true) {
            int min_j = -1;
            for (int j : chain) {
                if (min_j == -1 || edge_c[j] < edge_c[min_j]) {
                    min_j = j;
                }
            }
            del(min_j);
            min_q[i] = (edge_c[min_j] + edge_c[i]) / 2 + 1;
            chain.clear();
        } else {
            min_q[i] = 1;
        }
        add(i);
    }
    for (int u = 1; u <= N; u++) {
        adj[u].clear();
    }
    for (int k = M; k >= 1; k--) {
        int i = order[k]; int u = edge_u[i], v = edge_v[i];
        if (dfs(u, v) == true) {
            int max_j = -1;
            for (int j : chain) {
                if (max_j == -1 || edge_c[j] > edge_c[max_j]) {
                    max_j = j;
                }
            }
            del(max_j);
            max_q[i] = (edge_c[max_j] + edge_c[i]) / 2;
            chain.clear();
        } else {
            max_q[i] = INF;
        }
        add(i);
    }
    for (int i = 1; i <= M; i++) {
        update(Fen_cnt_l, min_q[i], edge_c[i], 1);
        update(Fen_sum_l, min_q[i], edge_c[i], edge_c[i]);
        update(Fen_sum_r, edge_c[i] + 1, max_q[i], edge_c[i]);
    }
    cin >> Q;
    while (Q--) {
        int X;
        cin >> X;
        ll sum_l = query(Fen_sum_l, X);
        ll sum_r = query(Fen_sum_r, X);
        int cnt_l = query(Fen_cnt_l, X);
        int cnt_r = (N - 1) - cnt_l;
        cout << (sum_l - (ll) cnt_l * X) + ((ll) cnt_r * X - sum_r) << "\n";
    }

    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 2 ms 2520 KB Output is correct
16 Correct 2 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 2 ms 2520 KB Output is correct
16 Correct 2 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 2840 ms 164180 KB Output is correct
21 Correct 2565 ms 164220 KB Output is correct
22 Correct 2682 ms 163984 KB Output is correct
23 Correct 2752 ms 164016 KB Output is correct
24 Correct 2730 ms 163984 KB Output is correct
25 Correct 2778 ms 163964 KB Output is correct
26 Correct 2922 ms 164508 KB Output is correct
27 Correct 2854 ms 159452 KB Output is correct
28 Correct 846 ms 7552 KB Output is correct
29 Correct 608 ms 4392 KB Output is correct
30 Correct 2813 ms 163988 KB Output is correct
31 Correct 2847 ms 164140 KB Output is correct
32 Correct 2742 ms 164116 KB Output is correct
33 Correct 2895 ms 164336 KB Output is correct
34 Correct 535 ms 4796 KB Output is correct
35 Correct 2814 ms 164376 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Execution timed out 5042 ms 409268 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 2 ms 2520 KB Output is correct
16 Correct 2 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Execution timed out 5069 ms 539632 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 2 ms 2520 KB Output is correct
16 Correct 2 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 2840 ms 164180 KB Output is correct
21 Correct 2565 ms 164220 KB Output is correct
22 Correct 2682 ms 163984 KB Output is correct
23 Correct 2752 ms 164016 KB Output is correct
24 Correct 2730 ms 163984 KB Output is correct
25 Correct 2778 ms 163964 KB Output is correct
26 Correct 2922 ms 164508 KB Output is correct
27 Correct 2854 ms 159452 KB Output is correct
28 Correct 846 ms 7552 KB Output is correct
29 Correct 608 ms 4392 KB Output is correct
30 Correct 2813 ms 163988 KB Output is correct
31 Correct 2847 ms 164140 KB Output is correct
32 Correct 2742 ms 164116 KB Output is correct
33 Correct 2895 ms 164336 KB Output is correct
34 Correct 535 ms 4796 KB Output is correct
35 Correct 2814 ms 164376 KB Output is correct
36 Correct 3217 ms 174544 KB Output is correct
37 Correct 2847 ms 174776 KB Output is correct
38 Correct 3390 ms 221124 KB Output is correct
39 Correct 3031 ms 174984 KB Output is correct
40 Correct 2944 ms 174808 KB Output is correct
41 Correct 3526 ms 221064 KB Output is correct
42 Correct 3094 ms 174756 KB Output is correct
43 Correct 3094 ms 170268 KB Output is correct
44 Correct 940 ms 23364 KB Output is correct
45 Correct 690 ms 24748 KB Output is correct
46 Correct 3495 ms 220996 KB Output is correct
47 Correct 3575 ms 221120 KB Output is correct
48 Correct 3571 ms 221224 KB Output is correct
49 Correct 3580 ms 221168 KB Output is correct
50 Correct 628 ms 24728 KB Output is correct
51 Correct 2852 ms 167188 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 2 ms 2520 KB Output is correct
16 Correct 2 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 2840 ms 164180 KB Output is correct
21 Correct 2565 ms 164220 KB Output is correct
22 Correct 2682 ms 163984 KB Output is correct
23 Correct 2752 ms 164016 KB Output is correct
24 Correct 2730 ms 163984 KB Output is correct
25 Correct 2778 ms 163964 KB Output is correct
26 Correct 2922 ms 164508 KB Output is correct
27 Correct 2854 ms 159452 KB Output is correct
28 Correct 846 ms 7552 KB Output is correct
29 Correct 608 ms 4392 KB Output is correct
30 Correct 2813 ms 163988 KB Output is correct
31 Correct 2847 ms 164140 KB Output is correct
32 Correct 2742 ms 164116 KB Output is correct
33 Correct 2895 ms 164336 KB Output is correct
34 Correct 535 ms 4796 KB Output is correct
35 Correct 2814 ms 164376 KB Output is correct
36 Correct 1 ms 2392 KB Output is correct
37 Correct 1 ms 2392 KB Output is correct
38 Correct 1 ms 2396 KB Output is correct
39 Execution timed out 5042 ms 409268 KB Time limit exceeded
40 Halted 0 ms 0 KB -