Submission #1087937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087937		vladilius	Reconstruction Project (JOI22_reconstruction)	C++17	31 / 100	330 ms	427600 KiB

reconstruction

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const int inf = 1e9 + 5;
const int N = 5e2;

struct dsu{
    int sz[N + 1], p[N + 1];
    int n;
    void init(int ns){
        n = ns;
        for (int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
    }
    bool same(int x, int y){
        return get(x) == get(y);
    }
    void clear(){
        for (int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m; cin>>n>>m;
    vector<arr3> ed;
    for (int i = 1; i <= m; i++){
        int a, b, w; cin>>a>>b>>w;
        ed.pb({a, b, w});
    }
    
    int q; cin>>q;
    vector<int> x(q + 1);
    vector<ll> out(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>x[i];
    }
    
    auto cmp = [&](arr3& x, arr3& y){
        return x[2] < y[2];
    };
    sort(ed.begin(), ed.end(), cmp);
    vector<int> ws;
    for (int i = 0; i < m; i++) ws.pb(ed[i][2]);
    
    vector<int> :: iterator it1, it2;
    dsu T[m];
    for (int i = 0; i < m; i++) T[i].init(n);
    
    vector<ll> p1(q + 2);
    vector<int> p2(q + 2);
    
    for (int i = m - 1; i >= 0; i--){
        auto [a, b, w] = ed[i];

        int l = i, r = m - 1;
        while (l + 1 < r){
            int k = (l + r) / 2;
            if (T[k].same(a, b)){
                r = k - 1;
            }
            else {
                l = k;
            }
        }
        if (!T[r].same(a, b)) l = r;
        
        if (m <= 1000){
            if (l == (m - 1)) l = inf;
            else l = (ws[l + 1] + w - 1) / 2;
            
            it1 = lower_bound(x.begin() + 1, x.end(), w);
            it2 = upper_bound(x.begin() + 1, x.end(), l);
            l = (int) (it1 - x.begin()); r = (int) (it2 - x.begin());
            if (l > r) continue;
            p1[l] -= w; p1[r] += w;
            p2[l]++; p2[r]--;
            
            for (int j = i; j < m; j++){
                if (T[j].same(a, b)) continue;
                T[j].unite(a, b);
            }
        }
    }
    
    if (m > 1000) return 0;
    
    for (int i = 0; i < m; i++) T[i].clear();
    
    for (int i = 0; i < m; i++){
        auto [a, b, w] = ed[i];
        
        int l = 0, r = i;
        while (l + 1 < r){
            int k = (l + r) / 2;
            if (T[k].same(a, b)){
                l = k + 1;
            }
            else {
                r = k;
            }
        }
        if (!T[l].same(a, b)) r = l;

        if (!r) r = 0;
        else r = (ws[r - 1] + w + 1) / 2;
 
        it1 = lower_bound(x.begin() + 1, x.end(), r);
        it2 = lower_bound(x.begin() + 1, x.end(), w);
        l = (int) (it1 - x.begin()); r = (int)(it2 - x.begin());
        if (l > r) continue;
        p1[l] += w; p1[r] -= w;
        p2[l]--; p2[r]++;

        for (int j = i; j >= 0; j--){
            if (T[j].same(a, b)) continue;
            T[j].unite(a, b);
        }
    }
    
    ll s1 = 0; int s2 = 0;
    for (int i = 1; i <= q; i++){
        s1 += p1[i];
        s2 += p2[i];
        cout<<1LL * x[i] * s2 + s1<<"\n";
    }
}

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