Submission #674522

#	Time	Username	Problem	Language	Result	Execution time	Memory
674522		someone	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	2485 ms	67468 KiB

reconstruction

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
struct Arc {
    int a, b, pds, i;
    
    bool operator <(const Arc& other) const {
        return pds < other.pds;
    }
};
 
struct Req {
    int q, i, add;
};
 
const int Q = 1e6 + 42, N = 542, M = 1e5 + 42, MOD = 1e9 + 7, INF = 1e12 + 42;
 
deque<Req> req;
deque<Arc> arc, mst;
int n, m, q, par[N], ans[Q], deb[M], fin[M], w[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;
}
 
set<pair<int, int>> val;

void add(Arc edge) {
    for(int i = 0; i < n; i++)
        par[i] = -1;
    U(edge.a, edge.b);
    for(int i = 0; i < n-1; i++) {
        if(!U(mst[i].a, mst[i].b)) {
            int mid = (edge.pds + mst[i].pds) >> 1;
            fin[edge.i] = mid;
            if(mst[i].i != -1)
                deb[mst[i].i] = mid;
            mst.erase(mst.begin() + i);
            break;
        }
    }
    mst.push_front(edge);
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    mt19937 rng(42);
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b >> w[i];
        a--, b--;
        arc.push_back({a, b, w[i] << 1, i});
    }
    cin >> q;
    for(int i = 0; i < q; i++) {
        int rq; cin >> rq;
        req.push_back({rq << 1, i, 0});
    }
    
    for(int i = 1; i < n; i++)
        mst.push_back({i-1, i, INF, -1});
    sort(arc.begin(), arc.end());
    for(int i = m-1; i >= 0 && !req.empty(); i--)
        add(arc[i]);
        
    for(int i = 0; i < m; i++) {
        req.push_back({deb[i], -1, w[i]});
        req.push_back({fin[i], -1, -w[i]});
    }
    
    sort(req.begin(), req.end(),
    [](Req a, Req b) {
        if(a.q == b.q) {
            if(a.i == b.i)
                return a.add > b.add;
            return a.i < b.i;
        }
        return a.q < b.q;
    });
    
    vector<int> mst;
    for(Req r : req) {
        if(r.i == -1) {
            if(r.add > 0) {
                mst.push_back(r.add);
            } else {
                int sz = mst.size();
                for(int i = 0; i < sz; i++)
                    if(mst[i] == -r.add) {
                        mst.erase(mst.begin() + i);
                        break;
                    }
            }
        } else {
            r.q >>= 1;
            for(int i : mst)
                ans[r.i] += abs(i - r.q);
        }
    }
    
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

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