Submission #546139

#	Time	Username	Problem	Language	Result	Execution time	Memory
546139		leaked	Reconstruction Project (JOI22_reconstruction)	C++14	42 / 100	5082 ms	433996 KiB

reconstruction

#include <bits/stdc++.h>

#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define m_p make_pair
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e6+1;
const int inf=1e9+1;
int p[N],sz[N];
vec<array<int,3>> torall;
void make(int v){
    p[v]=v;sz[v]=1;
}
int get(int v){
    return (p[v]==v?v:get(p[v]));
}
int tmr;
bool mg(int a,int b){
    a=get(a),b=get(b);
    if(a==b) return 0;

    torall.pb({tmr,a,sz[a]});
    torall.pb({tmr,b,sz[b]});

    if(sz[a]<sz[b]) swap(a,b);
    p[b]=a;sz[a]+=sz[b];
    return 1;
}


vec<int> kek;
struct fenwick{
    ll fnw[N];
    fenwick(){
        fill(fnw,fnw+N,0);
    }
    void upd(int i,int x){
        i=upper_bound(all(kek),i)-kek.begin()-1;
        ++i;
        while(i<=sz(kek)){
            fnw[i]+=x;
            i+=i&-i;
        }
    }
    ll get(int i){
        i=upper_bound(all(kek),i)-kek.begin()-1;
        ++i;
        ll ans=0;
        while(i>0){
            ans+=fnw[i];
            i-=i&-i;
        }
        return ans;
    }
    ll get(int l,int r){
        return get(r)-get(l-1);
    }
}fi,si;

ll ans[N];
array<int,3> arr[N];
int x[N];
int cnt[N];
void rec(const vec<int> &cur,int v,int tl,int tr){
    vec<int> ncur;
    tmr=v;
    for(auto &z : cur) cnt[z]=0;
    auto f=[&](int x){
        ncur=cur;
//        if(tl==0 && tr==1)
//            assert(!sz(torall));
//        cerr<<"DEBUG "<<sz(ncur)<<' '<<x<<endl;
        sort(all(ncur),[&](int i,int j){return abs(arr[i][0]-x)<abs(arr[j][0]-x);});
//        for(auto &z : ncur) make(arr[z][1]),make(arr[z][2]);
        for(auto &z : ncur){
//            cout<<"KEY "<<abs(arr[z][0]-x)<<endl;
            if(mg(arr[z][1],arr[z][2])){
                ++cnt[z];
            }
        }
        while(sz(torall) && torall.back()[0]==v){
            int u=torall.back()[1];sz[u]=torall.back()[2];p[u]=u;
            torall.pop_back();
        }
    };
//    for(auto &z : cur)
////        cout<<"HEY "<<z<<endl;
//    cout<<endl;
    f(x[tl]);f(x[tr]);

    vec<int> del;
    ncur.clear();
    for(auto &z : cur){
        if(cnt[z]==2){
            del.pb(z);
            mg(arr[z][1],arr[z][2]);
//            cout<<"DEL "<<arr[z][0]<<' '<<tl<<' '<<tr<<' '<<arr[z][1]<<' '<<arr[z][2]<<endl;
        }
//        else ncur.pb(z);
    }
    for(auto &z : cur){
        if(get(arr[z][1])!=get(arr[z][2])){
            ncur.pb(z);
//            mg(arr[z][1],arr[z][2]);
//            cout<<"DEL "<<arr[z][0]<<' '<<tl<<' '<<tr<<' '<<arr[z][1]<<' '<<arr[z][2]<<endl;
        }
//        else ncur.pb(z);
    }
//    cout<<endl;
    ///szhat'
    for(auto &z : del) fi.upd(arr[z][0],1),si.upd(arr[z][0],arr[z][0]);
    if(tl==tr){
        ans[tl]=si.get(x[tl],inf)-1ll*fi.get(x[tl],inf)*x[tl]
            -si.get(0,x[tl]-1)+1ll*fi.get(0,x[tl]-1)*x[tl];
    }
    else{
        int tm=(tl+tr)>>1;
        rec(ncur,2*v,tl,tm);
        rec(ncur,2*v+1,tm+1,tr);
    }
    for(auto &z : del) fi.upd(arr[z][0],-1),si.upd(arr[z][0],-arr[z][0]);
    while(sz(torall) && torall.back()[0]==v){
        int u=torall.back()[1];sz[u]=torall.back()[2];p[u]=u;
        torall.pop_back();
    }
}

void make1(int v){
    p[v]=v;sz[v]=1;
}
int get1(int v){
    return p[v]=(p[v]==v?v:get(p[v]));
}
bool mg1(int a,int b){
    a=get1(a),b=get1(b);
    if(a==b) return 0;
    if(sz[a]<sz[b]) swap(a,b);
    p[b]=a;sz[a]+=sz[b];
    return 1;
}

signed main(){
    fast_prep;
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int v,u,w;
        cin>>v>>u>>w;--v;--u;
        arr[i]={w,v,u};
        kek.pb(w);
    }
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    int q;cin>>q;
    for(int i=0;i<q;i++) cin>>x[i];
    if(q<=1000){
        for(int i=0;i<n;i++) make(i);
        vec<int> p(m);iota(all(p),0);
        rec(p,1,0,q-1);
        for(int i=0;i<q;i++)
            cout<<ans[i]<<'\n';
        return 0;
    }

    arr[m]={(int)-inf-10,0,0};
    sort(arr,arr+m+1);m++;
    vec<vec<int>> lft(m+1);

    auto rgt=lft;
    /// let's try
    {
        vec<int> cur;
        for(int i=m-1;i>=0;i--){
            for(int j=0;j<n;j++) make1(j);
            cur.insert(cur.begin(),i);
            for(int j=0;j<sz(cur);j++){
                if(mg1(arr[cur[j]][1],arr[cur[j]][2]))
                    rgt[i].pb(cur[j]);
                else{
                    for(int k=j+1;k<sz(cur);k++)
                        rgt[i].pb(cur[k]);
                    break;
                }
            }
            cur=rgt[i];
        }
    }
    {
        vec<int> cur;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++) make1(j);
            cur.insert(cur.begin(),i);
            for(int j=0;j<sz(cur);j++){
                if(mg1(arr[cur[j]][1],arr[cur[j]][2]))
                    lft[i].pb(cur[j]);
                else{
                    for(int k=j+1;k<sz(cur);k++)
                        lft[i].pb(cur[k]);
                    break;
                }
            }
            cur=lft[i];
        }
    }
    vec<int> kek;
    int j;
    vec<int> lower;
    vec<int> same;
    for(int i=0;i<q;i++) kek.pb(x[i]);
//    kek=x;
    vec<array<int,3>> my;
    for(int i=1;i<q;i++) assert(kek[i]>kek[i-1]);
    for(int j=1;j<m;j++) assert(arr[j][0]>=arr[j-1][0]);
    j=-1;
    int u=0;
    for(auto &z : kek){
        while(j+1<m && arr[j+1][0]<=z) ++j;
//        cout<<"HEY "<<z<<' '<<arr[j][0]<<' '<<arr[j+1][0]<<' '<<z<<endl;
        ///j and j+1
        int f=0,s=0;
        for(int i=0;i<n;i++) make(i);
        int rem=n-1;
        int lw=0;
        ll cur=0;
        int _sam=0;
//        assert(arr[j+1][0]>z && arr[j][0]<=z);
        while(rem--){
            while(f!=sz(lft[j]) && get1(arr[lft[j][f]][1])==get1(arr[lft[j][f]][2])) ++f;
            while(s!=sz(rgt[j+1]) && get1(arr[rgt[j+1][s]][1])==get1(arr[rgt[j+1][s]][2])) ++s;
            if(s!=sz(rgt[j+1]) && (f==sz(lft[j]) || (z-arr[lft[j][f]][0])>(arr[rgt[j+1][s]][0]-z))){
                assert(mg1(arr[rgt[j+1][s]][1],arr[rgt[j+1][s]][2]));
                cur+=arr[rgt[j+1][s]][0]-z;
                ++s;
            }
            else{
                assert(mg1(arr[lft[j][f]][1],arr[lft[j][f]][2]));

                cur+=z-arr[lft[j][f]][0];

                ++f;
            }
        }
        ans[u++]=cur;
//        ans.pb(cur);
    }
    for(int i=0;i<q;i++){
        int xt=x[i];
        ll anst=1e18;
        int j=i;
        cout<<ans[j]<<'\n';
    }
    return 0;
}
/*
5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
3
3
6
13
17

5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
1
10
17
*/

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:234:13: warning: unused variable 'lw' [-Wunused-variable]
  234 |         int lw=0;
      |             ^~
reconstruction.cpp:236:13: warning: unused variable '_sam' [-Wunused-variable]
  236 |         int _sam=0;
      |             ^~~~
reconstruction.cpp:258:13: warning: unused variable 'xt' [-Wunused-variable]
  258 |         int xt=x[i];
      |             ^~
reconstruction.cpp:259:12: warning: unused variable 'anst' [-Wunused-variable]
  259 |         ll anst=1e18;
      |            ^~~~

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