Submission #727729

#	Time	Username	Problem	Language	Result	Execution time	Memory
727729		fatemetmhr	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	963 ms	395164 KiB

reconstruction

// Be name khoda //

#include <bits/stdc++.h>


using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair

const int maxn5 = 1e6 + 10;
const int maxnt = 4e6 + 10;

ll lim, cnt[maxn5][2], sum[maxn5][2], c[maxn5], x[maxn5];
vector <int> av[maxnt][3];
int par[maxn5], edpt = 0, ed[maxn5], a[maxn5];
int l[maxn5], r[maxn5], b[maxn5], pt[maxn5];
vector <pair<int, pair<int, int>>> ch;
bool mark[maxn5];

inline bool cmp(int i, int j){return abs(c[i] - lim) < abs(c[j] - lim) || (abs(c[i] - lim) == abs(c[j] - lim) && i < j);}
inline int get_par(int a){
    while(par[a] >= 0)
        a = par[a];
    return a;
}

inline void undo(int k){
    while(ch.size() > k){
        int a = ch.back().fi;
        int b = par[a];
        par[b] = ch.back().se.se;
        par[a] = ch.back().se.fi;
        ch.pop_back();
    }
}

inline bool merge(int a, int b){
    a = get_par(a);
    b = get_par(b);
    if(a == b)
        return false;
    if(-par[a] > -par[b])
        swap(a, b);
    ch.pb({a, {par[a], par[b]}});
    if(par[a] == par[b])
        par[b]--;
    par[a] = b;
    return true;
}

inline void mst(int x){
    lim = x;
    sort(ed, ed + edpt, cmp);
    int keep = ch.size();
    for(int i = 0; i < edpt; i++)
        mark[ed[i]] = merge(a[ed[i]], b[ed[i]]);
    undo(keep);
}

void solve(int lq, int rq, int v){
    int mid = (lq + rq) >> 1;
    edpt = 0;
    for(int i = 0; i < 3; i++)
        for(auto id : av[v][i])
            ed[edpt++] = id;
    mst(x[mid]);
    if(rq - lq == 1){
        for(auto id : av[v][0]){
            if(mark[id])
                r[id] = lq;
            else
                r[id] = lq - 1;
        }
        for(auto id : av[v][1]){
            if(mark[id])
                l[id] = r[id] = lq;
            else{
                l[id] = rq;
                r[id] = lq;
            }
        }
        for(auto id : av[v][2]){
            if(mark[id])
                l[id] = lq;
            else
                l[id] = rq;
        }
        return;
    }
    int keep = ch.size();
    for(auto id : av[v][0]){
        if(mark[id]){
            merge(a[id], b[id]);
            av[v * 2 + 1][0].pb(id);
        }
        else
            av[v * 2][0].pb(id);
    }
    for(auto id : av[v][1]){
        if(mark[id]){
            av[v * 2][2].pb(id);
            av[v * 2 + 1][0].pb(id);
        }
        else{
            if(pt[id] < mid)
                av[v * 2][1].pb(id);
            else
                av[v * 2 + 1][1].pb(id);
        }
    }
    vector <int> tomerge;
    for(auto id : av[v][2]){
        if(mark[id]){
            av[v * 2][2].pb(id);
            tomerge.pb(id);
        }
        else
            av[v * 2 + 1][2].pb(id);
    }
    solve(lq, mid, v * 2);
    undo(keep);
    for(auto id : tomerge)
        merge(a[id], b[id]);
    solve(mid, rq, v * 2 + 1);
    undo(keep);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    memset(par, -1, sizeof par);

    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        av[1][1].pb(i);
    }
    int q; cin >> q;
    for(int i = 0; i < q; i++)
        cin >> x[i];
    for(int i = 0; i < m; i++)
        pt[i] = upper_bound(x, x + q, c[i]) - x - 1;
    solve(0, q, 1);
    for(int i = 0; i < m; i++) if(l[i] <= r[i]){
        if(x[l[i]] <= c[i]){
            cnt[l[i]][0]++;
            sum[l[i]][0] += c[i];
        }
        else{
            cnt[l[i]][1]++;
            sum[l[i]][1] -= c[i];
        }
        if(x[r[i]] <= c[i]){
            cnt[r[i] + 1][0]--;
            sum[r[i] + 1][0] -= c[i];
        }
        else{
            cnt[r[i] + 1][1]--;
            sum[r[i] + 1][1] += c[i];
        }
        if(x[l[i]] <= c[i] && x[r[i]] > c[i]){
            cnt[pt[i] + 1][0]--;
            sum[pt[i] + 1][0] -= c[i];
            cnt[pt[i] + 1][1]++;
            sum[pt[i] + 1][1] -= c[i];
        }
    }
    ll cur[2] = {0, 0}, t[2] = {0, 0};
    for(int i = 0; i < q; i++){
        cur[0] += sum[i][0];
        cur[1] += sum[i][1];
        t[0] += cnt[i][0];
        t[1] += cnt[i][1];
        cout << cur[0] + cur[1] + t[0] * (-x[i]) + t[1] * x[i] << '\n';
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'void undo(int)':
reconstruction.cpp:34:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     while(ch.size() > k){
      |           ~~~~~~~~~~^~~

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