Submission #886388

#	Time	Username	Problem	Language	Result	Execution time	Memory
886388		dong_liu	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	4775 ms	428548 KiB

reconstruction

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using u64 = unsigned long long;
using pii = pair<int, int>;

bool mem_st;

const int N = 500, M = 1e5, Q = 1e6;

struct edge {
    int i, j, w;
    bool operator<(const edge e) const {
        return w < e.w;
    }
};

struct arr : ar<int, N-1> {
    int sz = 0;
    void pb(int x) { at(sz++) = x; }
    auto end() { return begin()+sz; }
};

int n, m, q;
edge e[M];
arr pf[M+1], sf[M+1];

struct {
    int p[N];
    void init() {
        for (int i = 0; i < n; i++) p[i] = i;
    }
    int find(int i) {
        return p[i] == i ? i : p[i] = find(p[i]);
    }
    bool join(int i, int j) {
        i = find(i), j = find(j);
        if (i == j) return false;
        p[i] = j;
        return true;
    }
} dsu;

mt19937 rng(12345);

int ran(int l, int r) { return l+rng()%(r-l+1); }

void log_time() {
    cerr << "Time: " << double(clock()) / CLOCKS_PER_SEC << '\n';
}

u64 hsh[M], hh[Q];
int xx[Q], tt[Q]; i64 ans[Q];

void solve(int qq) {
    int x = xx[qq];
    int t = tt[qq];
    dsu.init();
    int one = 0, two = 0;
    #define ins(h) if (dsu.join(e[h].i, e[h].j)) ans[qq] += abs(e[h].w-x), hh[qq] ^= hsh[h]
    while (one < pf[t].sz && two < sf[t].sz)
        if (2*x-e[pf[t][one]].w < e[sf[t][two]].w) {ins(pf[t][one]); one++;}
        else {ins(sf[t][two]); two++;}
    while (one < pf[t].sz) {ins(pf[t][one]); one++;}
    while (two < sf[t].sz) {ins(sf[t][two]); two++;}
    #undef ins
}

void solve(int l, int r) {
    if (r-l <= 1) return;
    if (hh[l] == hh[r]) {
        static arr w, u;
        w.sz = 0;
        u.sz = 0;
        int x = xx[l];
        int t = tt[l];
        dsu.init();
        int one = 0, two = 0;
        #define ins(ww,h) if (dsu.join(e[h].i, e[h].j)) ww.pb(e[h].w)
        while (one < pf[t].sz && two < sf[t].sz)
            if (2*x-e[pf[t][one]].w < e[sf[t][two]].w) {ins(w,pf[t][one]); one++;}
            else {ins(u,sf[t][two]); two++;}
        while (one < pf[t].sz) {ins(w,pf[t][one]); one++;}
        while (two < sf[t].sz) {ins(u,sf[t][two]); two++;}
        #undef ins
        {
            i64 suf = 0;
            for (int x : w) suf += x;
            i64 pre = 0; int h = 0;
            for (int i = l+1; i < r; i++) {
                while (h < w.sz && w[w.sz-h-1] <= xx[i]) {
                    pre += w[w.sz-h-1];
                    suf -= w[w.sz-h-1];
                    h++;
                }
                ans[i] = i64(xx[i]) * h - pre + suf - i64(xx[i]) * (w.sz-h);
            }
        }
        {
            i64 suf = 0;
            for (int x : u) suf += x;
            i64 pre = 0; int h = 0;
            for (int i = l+1; i < r; i++) {
                while (h < u.sz && u[h] <= xx[i]) {
                    pre += u[h];
                    suf -= u[h];
                    h++;
                }
                ans[i] += i64(xx[i]) * h - pre + suf - i64(xx[i]) * (u.sz-h);
            }
        }
    } else {
        int m = (l+r)/2;
        solve(m);
        solve(l,m), solve(m,r);
    }
}

bool mem_en;

#define MAX

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef MAX
    n = N;
    m = 2e4;
#else
    cin >> n >> m;
#endif
    mt19937_64 rng_big(1234);
    for (int h = 0; h < m; h++) {
        hsh[h] = rng_big();
#ifdef MAX
        if (h < n-1) e[h].i = h+1, e[h].j = h+2;
        else e[h].i = ran(1,n), e[h].j = ran(1,n);
        e[h].w = ran(1,1e9);
#else
        cin >> e[h].i >> e[h].j >> e[h].w;
#endif
        e[h].i--, e[h].j--;
    }
    sort(e, e+m);
    for (int t = 1; t <= m; t++) {
        auto ins = [&](int h) {
            if (dsu.join(e[h].i, e[h].j))
                pf[t].pb(h);
        };
        dsu.init();
        ins(t-1);
        for (int h : pf[t-1]) ins(h);
    }
    for (int t = m-1; t >= 0; t--) {
        auto ins = [&](int h) {
            if (dsu.join(e[h].i, e[h].j))
                sf[t].pb(h);
        };
        dsu.init();
        ins(t);
        for (int h : sf[t+1]) ins(h);
    }
#ifdef LOCAL
    cerr << "AFTER BUILD" << endl;
    log_time();
#endif
    i64 work = 0;
#ifdef MAX
    q = Q;
#else
    cin >> q;
#endif
    int t = 0;
    for (int qq = 0; qq < q; qq++) {
#ifdef MAX
        xx[qq] = (1e9/q) * (qq+1);
#else
        cin >> xx[qq];
#endif
        while (t < m && e[t].w <= xx[qq]) t++;
        tt[qq] = t;
    }
    // for (int h = 0; h < q; h++) {
    //     solve(h);
    //     cout << hh[h] << endl;
    // }
    solve(0);
    solve(q-1);
    solve(0, q-1);
    for (int h = 0; h < q; h++) cout << ans[h] << '\n';
#ifdef LOCAL
    cerr << "Work: " << work << endl;
    cerr << "Memory: " << double(&mem_en - &mem_st) / (1 << 20) << '\n';
    log_time();
#endif
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:170:9: warning: unused variable 'work' [-Wunused-variable]
  170 |     i64 work = 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