Submission #951554

#	Time	Username	Problem	Language	Result	Execution time	Memory
951554		Pring	Reconstruction Project (JOI22_reconstruction)	C++17	10 / 100	271 ms	69104 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
typedef array<int, 3> p3i;

const int MXN = 505, MXM = 100005, MXQ = 1000005;
int n, m, q;
int eu[MXM], ev[MXM], ew[MXM], qry[MXQ];

struct DSU {
    int p[MXN];
    void init(int n) {
        fill(p + 1, p + n + 1, -1);
    }
    int find(int x) {
        return (p[x] < 0 ? x : p[x] = find(p[x]));
    }
    bool onion(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (p[x] > p[y]) swap(x, y);
        p[x] += p[y];
        p[y] = x;
        return true;
    }
};

namespace SB12 {
    p3i edge[MXN];
    DSU dsu;

    int calc(int x) {
        FOR(i, 0, m) edge[i] = {abs(x - ew[i]), eu[i] ,ev[i]};
        sort(edge, edge + m);
        dsu.init(n);
        int ans = 0;
        FOR(i, 0, m) {
            auto &[w, u, v] = edge[i];
            if (dsu.onion(u, v)) ans += w;
        }
        return ans;
    }

    void solve() {
        FOR(i, 0, q) cout << calc(qry[i]) << '\n';
    }
}

namespace SB3 {
    p3i edge[MXM];
    vector<pii> op;
    int ans[MXQ];
    int d;

    bool check() {
        FOR(i, 0, m) if (ev[i] != eu[i] + 1) return false;
        return true;
    }

    int process(int l, int r) {
        vector<int> v;
        int sml = INT_MAX;
        FOR(i, l, r) {
            v.push_back(edge[i][2]);
        }
        sort(v.begin(), v.end());
        for (auto &i : v) {
            op.push_back(mp(i, -1LL));
            op.push_back(mp(i, -1LL));
        }
        FOR(i, 1, v.size()) {
            int x = v[i - 1], y = v[i];
            op.push_back(mp(x + (y - x) / 2, -2LL));
            op.push_back(mp(x + (y - x) / 2 + (y - x) % 2, -2LL));
        }
        return v.front();
    }

    void solve() {
        assert(check());
        FOR(i, 0, m) edge[i] = {eu[i], ev[i], ew[i]};
        sort(edge, edge + m);
        int cost = 0;
        for (int i = 0, j = 0; i < m; i = j) {
            while (j < m && edge[i][0] == edge[j][0]) j++;
            cost += process(i, j);
        }
        FOR(i, 0, q) op.push_back(mp(qry[i], i));
        sort(op.begin(), op.end());
        int time = 0;
        d = -(n - 1);
        for (auto &[t, id] : op) {
            debug(t, id);
            cost += (t - time) * d;
            time = t;
            if (id == -2) {
                d--;
            } else if (id == -1) {
                d++;
            } else {
                ans[id] = cost;
            }
        }
        FOR(i, 0, q) cout << ans[i] << '\n';
    }
}

void miku() {
    cin >> n >> m;
    FOR(i, 0, m) {
        cin >> eu[i] >> ev[i] >> ew[i];
    }
    cin >> q;
    FOR(i, 0, q) cin >> qry[i];
    if (q <= 10) SB12::solve();
    else SB3::solve();
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'long long int SB3::process(long long int, long long int)':
reconstruction.cpp:79:13: warning: unused variable 'sml' [-Wunused-variable]
   79 |         int sml = INT_MAX;
      |             ^~~
reconstruction.cpp: In function 'void SB3::solve()':
reconstruction.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
reconstruction.cpp:110:13: note: in expansion of macro 'debug'
  110 |             debug(t, id);
      |             ^~~~~

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