Submission #1035264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035264		shenfe1	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	2248 ms	402016 KiB

reconstruction

#include <bits/stdc++.h>
 
#pragma GCC optimize("Ofast,unroll-loops")
 
using namespace std;
 
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define ppb pop_back
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define lb lower_bound
#define mem(a,i) memset(a,i,sizeof(a))

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MAX=1e5+10;
 
int n,m;
 
struct DSU{
    int f[MAX];
 
    void init(int n){
        for(int i=1;i<=n;i++)f[i]=i;
    }

    int get(int v){
        return (f[v]==v?v:f[v]=get(f[v]));
    }
 
    void unite(int a,int b){
        a=get(a);
        b=get(b);
        f[a]=b;
    }
}D;


struct segtree{
    ll t[120*MAX];
    int L[120*MAX],R[120*MAX];
    int zs;

    segtree(){
        mem(t,0);
        mem(L,0);
        mem(R,0);
        zs=1;
    }
    
    void update(int v,int tl,int tr,int l,int r,int x){
        if(l>r||tl>r||l>tr)return;
        if(l<=tl&&tr<=r){
            t[v]+=x;
            return;
        }
        int tm=(tl+tr)/2;
        if(!L[v]){
            L[v]=++zs;
        }
        if(!R[v]){
            R[v]=++zs;
        }
        update(L[v],tl,tm,l,r,x);
        update(R[v],tm+1,tr,l,r,x);
    }

    ll get(int v,int tl,int tr,int pos){
        if(tl==tr)return t[v];
        int tm=(tl+tr)/2;
        if(pos<=tm){
            if(L[v])return t[v]+get(L[v],tl,tm,pos);
            return t[v];
        }
        else{
            if(R[v])return t[v]+get(R[v],tm+1,tr,pos);
            return t[v];
        }
    }
}T[2];

vector<pair<int,pii>> e;
set<pii> g[510];
int d[510];

void dfs(int v,int p=-1){
    for(auto to:g[v]){
        if(to.F==p)continue;
        d[to.F]=max(d[v],to.S);
        dfs(to.F,v);
    }
}

void dfs1(int v,int p=-1){
    for(auto to:g[v]){
        if(to.F==p)continue;
        d[to.F]=min(d[v],to.S);
        dfs1(to.F,v);
    }
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        e.pb({c,{a,b}});
    }
    sort(all(e));
    D.init(n);
    for(int i=m-1;i>=0;i--){
        if(D.get(e[i].S.F)!=D.get(e[i].S.S)){
            D.unite(e[i].S.F,e[i].S.S);
            g[e[i].S.F].insert({e[i].S.S,i});
            g[e[i].S.S].insert({e[i].S.F,i});
            // if(e[i].F<=10)cout<<i<<" "<<10-e[i].F<<"\n";
            T[0].update(1,0,1e9,e[i].F,1e9,-e[i].F);
            T[1].update(1,0,1e9,e[i].F,1e9,1);
        }
        else{
            mem(d,0);
            dfs(e[i].S.F);
            int edge=d[e[i].S.S];
            g[e[edge].S.F].erase({e[edge].S.S,edge});
            g[e[edge].S.S].erase({e[edge].S.F,edge});
            {
                int pos=(e[i].F+e[edge].F)/2;
                // if(e[i].F<=10&&10<=pos)cout<<e[i].F<<" "<<e[edge].F<<" "<<pos<<" "<<10-e[i].F<<"\n";
                T[0].update(1,0,1e9,e[i].F,pos,-e[i].F);
                T[1].update(1,0,1e9,e[i].F,pos,1);
            }
            g[e[i].S.F].insert({e[i].S.S,i});
            g[e[i].S.S].insert({e[i].S.F,i});
        }
    }
    D.init(n);
    for(int i=0;i<m;i++){
        if(D.get(e[i].S.F)!=D.get(e[i].S.S)){
            D.unite(e[i].S.F,e[i].S.S);
            g[e[i].S.F].insert({e[i].S.S,i});
            g[e[i].S.S].insert({e[i].S.F,i});
            T[0].update(1,0,1e9,0,e[i].F,e[i].F);
            T[1].update(1,0,1e9,0,e[i].F,-1);
        }
        else{
            for(int i=1;i<=n;i++)d[i]=1e9;
            dfs1(e[i].S.F);
            int edge=d[e[i].S.S];
            g[e[edge].S.F].erase({e[edge].S.S,edge});
            g[e[edge].S.S].erase({e[edge].S.F,edge});
            {
                int pos=(e[edge].F+e[i].F)/2+1;
                T[0].update(1,0,1e9,pos,e[i].F,e[i].F);
                T[1].update(1,0,1e9,pos,e[i].F,-1);
            }    
            g[e[i].S.F].insert({e[i].S.S,i});
            g[e[i].S.S].insert({e[i].S.F,i});
        }
    }
    int q;
    cin>>q;
    while(q--){
        int d;
        cin>>d;
        cout<<T[0].get(1,0,1e9,d)+T[1].get(1,0,1e9,d)*d<<"\n";
    }
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    int init=clock();
    while(t--)solve();
    #ifdef LOCAL
        cout.precision(10);
        cout<<fixed<<1.0*(clock()-init)/CLOCKS_PER_SEC<<"\n";
    #endif
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:179:9: warning: unused variable 'init' [-Wunused-variable]
  179 |     int init=clock();
      |         ^~~~

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