Submission #1033928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033928		Alish	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	1239 ms	53596 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("tests.in" , "r" , stdin) ;

ll mod = 1e9+7;


const int N = 523, M=1e5+23, QQ=1e6+23;

int sz[N], par[N];
int L[M], R[M];
ll pref[QQ], small[QQ];
vector<ll> Q;
vector<pair<ll, pll> > E;
int n, m, q;


int getPar(int v){
    if(par[v]==-1) return v;
    return par[v]=getPar(par[v]);
}

bool Union(int u, int v){
    u=getPar(u);
    v=getPar(v);
    if(v==u) return 0;
    if(sz[v]<sz[u]) swap(u, v);
    par[u]=v;
    sz[v]+=sz[u];
    return 1;
}

int main()
{
    fast_io
    cin>>n>>m;
    for (int i=0; i<m; i++){
        int v, u, w;
        cin>>v>>u>>w;
        E.pb({w, {v, u}});
    }
    sort(all(E));
    cin>>q;
    for (int i=0; i<q; i++){
        int x; cin>>x;
        Q.pb(x);
    }

    for (int i=0; i<m; i++){
        int v=E[i].S.F, u=E[i].S.S;
        for (int j=1; j<=n; j++){
            par[j]=-1;
            sz[j]=1;
        }
        L[i]=-1;
        R[i]=m;
        for (int j=i-1; j>=0; j--)if(Union(E[j].S.F, E[j].S.S) && getPar(u)==getPar(v)){
            L[i]=j;
            break;
        }
        for (int j=1; j<=n; j++){
            par[j]=-1;
            sz[j]=1;
        }
        for (int j=i+1; j<m; j++)if(Union(E[j].S.F, E[j].S.S) && getPar(u)==getPar(v)){
            R[i]=j;
            break;
        }

    }

    for (int i=0; i<m; i++){
        int l=0, mid, r=q;
        if(L[i]!=-1) l=lower_bound(all(Q), (E[i].F+E[L[i]].F+1)/2)-Q.begin();
        pref[l]+=E[i].F;
        small[l]--;
        mid=lower_bound(all(Q), E[i].F)-Q.begin();
        pref[mid]-=2*E[i].F;
        small[mid]+=2;
        if(R[i]!=m) r=lower_bound(all(Q), (E[i].F+E[R[i]].F+1)/2)-Q.begin();
        pref[r]+=E[i].F;
        small[r]--;
    }
    for (int i=1; i<q; i++){
        pref[i]+=pref[i-1];
        small[i]+=small[i-1];
    }
    for (int i=0; i<q; i++) cout<<pref[i]+Q[i]*small[i]<<endl;

}
/*


*/

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