Submission #722889

#	Time	Username	Problem	Language	Result	Execution time	Memory
722889		becaido	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1037 ms	33476 KiB

reconstruction

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int INF = 1e9 + 1;
const int SIZE = 505;
const int MSIZ = 1e5 + 5;

int n, m, q;
int to[SIZE], h[SIZE];
int l[MSIZ], r[MSIZ];
int pa[SIZE], pid[SIZE], dep[SIZE];
tuple<int, int, int> e[MSIZ];
vector<pair<int, int>> adj[SIZE];
vector<pair<int, int>> dcnt, dsum;

int dsu(int x) {
    return x == to[x] ? x : (to[x] = dsu(to[x]));
}
bool Merge(int a, int b) {
    a = dsu(a), b = dsu(b);
    if (a == b) return 0;
    if (h[a] < h[b]) swap(a, b);
    to[b] = a;
    h[a] += h[a] == h[b];
    return 1;
}

void solve() {
    cin >> n >> m;
    FOR (i, 1, m) {
        auto &[w, a, b] = e[i];
        cin >> a >> b >> w;
    }
    sort(e + 1, e + m + 1);
    iota(to + 1, to + n + 1, 1);

    auto dfs = [&](auto dfs, int pos)->void {
        for (auto [np, id] : adj[pos]) if (np != pa[pos]) {
            pa[np] = pos;
            pid[np] = id;
            dep[np] = dep[pos] + 1;
            dfs(dfs, np);
        }
    };
    auto build = [&]() {
        fill(pa + 1, pa + n + 1, 0);
        FOR (i, 1, n) if (!pa[i]) {
            pid[i] = 0;
            dep[i] = 1;
            dfs(dfs, i);
        }
    };

    FOR (i, 1, m) {
        build();
        auto [w, a, b] = e[i];
        if (Merge(a, b)) {
            adj[a].pb(b, i);
            adj[b].pb(a, i);
            r[i] = INF;
            continue;
        }
        int mn = INF, id;
        for (int ca = a, cb = b; ca != cb; ca = pa[ca]) {
            if (dep[ca] < dep[cb]) swap(ca, cb);
            if (get<0>(e[pid[ca]]) < mn) {
                mn = get<0>(e[pid[ca]]);
                id = pid[ca];
            }
        }
        l[i] = (w + mn + 1) / 2;
        r[id] = l[i] - 1;
        r[i] = INF;
        int ca, cb;
        tie(w, ca, cb) = e[id];
        adj[ca].erase(find(adj[ca].begin(), adj[ca].end(), make_pair(cb, id)));
        adj[cb].erase(find(adj[cb].begin(), adj[cb].end(), make_pair(ca, id)));
        adj[a].pb(b, i);
        adj[b].pb(a, i);
    }
    FOR (i, 1, m) {
        auto [w, a, b] = e[i];
        if (r[i] <= w) {
            dcnt.pb(l[i], -1), dcnt.pb(r[i] + 1, 1);
            dsum.pb(l[i], w), dsum.pb(r[i] + 1, -w);
        } else if (l[i] >= w) {
            dcnt.pb(l[i], 1), dcnt.pb(r[i] + 1, -1);
            dsum.pb(l[i], -w), dsum.pb(r[i] + 1, w);
        } else {
            dcnt.pb(l[i], -1), dcnt.pb(w + 1, 1);
            dsum.pb(l[i], w), dsum.pb(w + 1, -w);
            dcnt.pb(w + 1, 1), dcnt.pb(r[i] + 1, -1);
            dsum.pb(w + 1, -w), dsum.pb(r[i] + 1, w);
        }
    }
    sort(dcnt.begin(), dcnt.end());
    sort(dsum.begin(), dsum.end());
    int cnt = 0;
    ll sum = 0;
    cin >> q;
    int p = 0;
    while (q--) {
        int x;
        cin >> x;
        while (p < dcnt.size() && dcnt[p].F <= x) {
            cnt += dcnt[p].S;
            sum += dsum[p].S;
            p++;
        }
        cout << sum + 1ll * cnt * x << '\n';
    }
}

int main() {
    Waimai;
    solve();
}

Compilation message (stderr)

reconstruction.cpp: In function 'void solve()':
reconstruction.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         while (p < dcnt.size() && dcnt[p].F <= x) {
      |                ~~^~~~~~~~~~~~~
reconstruction.cpp:81:23: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |         int mn = INF, id;
      |                       ^~

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