Submission #674460

#	Time	Username	Problem	Language	Result	Execution time	Memory
674460		someone	Reconstruction Project (JOI22_reconstruction)	C++14	42 / 100	5038 ms	96240 KiB

reconstruction

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

struct Arc {
    int a, b, pds;
    
    bool operator <(const Arc& other) const {
        return pds < other.pds;
    }
};

struct Req {
    int q, i, ans = 0;
};

const int N = 1e6 + 42, M = 542, INF = 1e18 + 42, MOD = 1e9 + 7;

Req req[N];
int n, m, q, par[M];

int F(int i) {
    if(par[i] < 0)
        return i;
    return par[i] = F(par[i]);
}

bool U(int a, int b) {
    a = F(a), b = F(b);
    if(a == b) return false;
    if(-par[a] < -par[b]) swap(a, b);
    
    par[a] += par[b];
    par[b] = a;
    return true;
}

void dpr(int deb, int fin, deque<Arc> arc) {
    if(deb == fin)
        return;
    int mid = (deb + fin) >> 1;
    deque<Arc> l, r;
    for(Arc a : arc)
        if(a.pds < req[mid].q)
            l.push_back(a);
        else
            r.push_back(a);
    
    int nb = n-1, sz = (int)r.size(),
        id[] = {((int)l.size())-1, 0};
    for(int i = 0; i < n; i++)
        par[i] = -1;
    while(nb) {
        if(id[1] < sz && (id[0] == -1 || req[mid].q - l[id[0]].pds > r[id[1]].pds - req[mid].q)) {
            if(U(r[id[1]].a, r[id[1]].b)) {
                nb--;
                l.push_back(r[id[1]]);
                req[mid].ans += r[id[1]].pds - req[mid].q;
            }
            id[1]++;
        } else {
            if(U(l[id[0]].a, l[id[0]].b)) {
                nb--;
                sz++, id[1]++;
                r.push_front(l[id[0]]);
                req[mid].ans += req[mid].q - l[id[0]].pds;
            }
            id[0]--;
        }
    }
    if(fin - deb == 1)
        return;
    dpr(deb, mid, l);
    dpr(mid+1, fin, r);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    deque<Arc> arc;
    for(int i = 0; i < m; i++) {
        int a, b, pds;
        cin >> a >> b >> pds;
        a--, b--;
        arc.push_back({a, b, pds});
    }
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> req[i].q;
        req[i].i = i;
    }
    sort(req, req + q,
    [](Req a, Req b) {
        return a.q < b.q;
    });
    sort(arc.begin(), arc.end());
    
    dpr(0, q, arc);
    
    sort(req, req + q,
    [](Req a, Req b) {
        return a.i < b.i;
    });
    for(int i = 0; i < q; i++)
        cout << req[i].ans << '\n';
}

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