Submission #958377

#	Time	Username	Problem	Language	Result	Execution time	Memory
958377		alextodoran	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	5097 ms	448300 KiB

reconstruction

/**
 _  _   __  _ _ _  _  _ _
 |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;

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 path[N_MAX + 2][N_MAX + 2];

int max_lower_path[M_MAX + 2];
int min_higher_path[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) {
    update(Fen, l, val);
    update(Fen, r + 1, -val);
}
int 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: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23