Submission #959395

#	Time	Username	Problem	Language	Result	Execution time	Memory
959395		alextodoran	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	955 ms	34468 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 + 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));
}

vector <pair <ll, int>> events_l, events_r;

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++) {
        events_l.push_back({min_q[i], edge_c[i]});
        events_l.push_back({edge_c[i] + 1, -edge_c[i]});
        events_r.push_back({edge_c[i], edge_c[i]});
        events_r.push_back({max_q[i] + 1, -edge_c[i]});
    }
    sort(events_l.begin(), events_l.end(), greater <pair <int, int>> ());
    sort(events_r.begin(), events_r.end(), greater <pair <int, int>> ());
    ll sum_l = 0, sum_r = 0;
    int cnt_l = 0, cnt_r = 0;
    cin >> Q;
    while (Q--) {
        int X;
        cin >> X;
        while (events_l.empty() == false && events_l.back().first <= X) {
            sum_l += events_l.back().second;
            cnt_l += (events_l.back().second > 0 ? +1 : -1);
            events_l.pop_back();
        }
        while (events_r.empty() == false && events_r.back().first <= X) {
            sum_r += events_r.back().second;
            cnt_r += (events_r.back().second > 0 ? +1 : -1);
            events_r.pop_back();
        }
        cout << (sum_l - (ll) cnt_l * X) + ((ll) cnt_r * X - sum_r) << "\n";
    }

    return 0;
}

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