Submission #1087924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087924		vladilius	Reconstruction Project (JOI22_reconstruction)	C++17	31 / 100	5109 ms	425404 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;

struct dsu{
    vector<int> sz, p;
    int n;
    void init(int ns){
        n = ns;
        sz.resize(n + 1);
        p.resize(n + 1);
        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 it, 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];
        
        auto check = [&](int x){
            int ww = w + 2 * (x - w);
            it = upper_bound(ws.begin(), ws.end(), ww); it--;
            int j = (int) (it - ws.begin());
            return T[j].same(a, b);
        };
        
        int l = w, r = inf;
        while (l + 1 < r){
            int m = (l + r) / 2;
            if (check(m)){
                r = m - 1;
            }
            else {
                l = m;
            }
        }
        if (!check(r)) l = r;
        if (check(l)) continue;
    
        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());
        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);
        }
    }
    
    for (int i = 0; i < m; i++) T[i].clear();
    
    for (int i = 0; i < m; i++){
        auto [a, b, w] = ed[i];
        
        auto check = [&](int x){
            int ww = 2 * x + 1 - w;
            it = lower_bound(ws.begin(), ws.end(), ww);
            int j = (int) (it - ws.begin());
            return T[j].same(a, b);
        };
        
        int l = 0, r = w - 1;
        while (l + 1 < r){
            int m = (l + r) / 2;
            if (check(m)){
                l = m + 1;
            }
            else {
                r = m;
            }
        }
        if (!check(l)) r = l;
        if (check(r)) continue;
        
        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());
        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