Submission #973457

#	Time	Username	Problem	Language	Result	Execution time	Memory
973457		hotboy2703	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	1070 ms	57680 KiB

reconstruction

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll MAXN = 500;
const ll MAXM = 1e5;
const ll INF = 1e9+7;
struct edge{
    ll u,v,w;
    bool operator == (const edge &p)const {
        return make_tuple(u,v,w) == make_tuple(p.u,p.v,p.w);
    }
};
edge all[MAXM+100];
pll query[1'000'100];
long long pf[2][1'000'100];
long long ans[1'000'100];
ll dsu[MAXN+100];
ll f(ll x){
    if (dsu[x] < 0)return x;
    return (dsu[x] = f(dsu[x]));
}
void join(ll x,ll y){
    x = f(x),y = f(y);
    if (x!=y){
        if (dsu[x] > dsu[y])swap(x,y);
        dsu[x] += dsu[y];
        dsu[y] = x;
    }
}
ll n,m,q;
pll range[MAXM+100];
vector <ll> mst;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
//    freopen("code1.inp","r",stdin);
    cin>>n>>m;
    for (ll i = 1;i <= m;i ++){
        cin>>all[i].u>>all[i].v>>all[i].w;
    }
    sort(all+1,all+1+m,[](edge x, edge y){return MP(x.w,MP(x.u,x.v)) < MP(y.w,MP(y.u,y.v));});
    m = unique(all+1,all+1+m)-all-1;
    cin>>q;
    for (ll i = 1;i <= q;i ++){
        cin>>query[i].fi;
        query[i].se = i;
    }
    sort(query+1,query+1+q);
    mst.clear();
    for (ll i = 1;i <= m;i ++){
//      	assert(sz(mst) < n);
        range[i].fi = -INF;
        for (ll j = 1;j <= n;j ++)dsu[j] = -1;
        ll ptr = 0;
        for (auto x:mst){
            join(all[x].u,all[x].v);
            if (f(all[i].u)==f(all[i].v)){
                mst.erase(mst.begin()+ptr);
                range[i].fi = (all[x].w + all[i].w) / 2 + 1;
                break;
            }
            ptr++;
        }
        mst.insert(mst.begin(),i);
    }
    mst.clear();
    for (ll i = m;i >= 1;i --){assert(sz(mst) < n);
        range[i].se = INF;
        for (ll j = 1;j <= n;j ++)dsu[j] = -1;
        ll ptr = 0;
        for (auto x:mst){
            join(all[x].u,all[x].v);
            if (f(all[i].u)==f(all[i].v)){
                mst.erase(mst.begin()+ptr);
                range[i].se = (all[x].w + all[i].w) / 2;
                break;
            }
            ptr++;
        }
        mst.insert(mst.begin(),i);
    }
//    for (ll i = 1;i <= m;i ++){
//        cout<<all[i].u<<' '<<all[i].v<<' ' <<all[i].w<<'\n';
//    }
//    for (ll i = 1;i <= m;i ++){
//        cout<<range[i].fi<<' '<<range[i].se<<'\n';
//    }
    for (ll i = 1;i <= m;i ++){
//        if (all[i].w >= range[i].fi){
            ll l = lower_bound(query+1,query+1+q,MP(range[i].fi,-1))-query;
            ll r = upper_bound(query+1,query+1+q,MP(range[i].se,INF))-query-1;
            ll mid = lower_bound(query+1,query+1+q,MP(all[i].w,-1))-query;
//            cout<<i<<' '<<l<<' '<<mid<<' '<<r<<'\n';
//            if (l <= r){

                if (l <= mid - 1){
                    // -1 * x + w
                    pf[1][l] += -1;
                    pf[1][mid] -= (-1);
                    pf[0][l] += all[i].w;
                    pf[0][mid] -= all[i].w;
                }
                if (mid <= r){
                    //+1 * x - w
                    pf[1][mid] += +1;
                    pf[1][r+1] -= (+1);
                    pf[0][mid] += -all[i].w;
                    pf[0][r+1] -= -all[i].w;
                }
//            }
//        }
    }
    for (ll i = 1;i <= q;i ++){
        pf[1][i] += pf[1][i-1];
        pf[0][i] += pf[0][i-1];
        ans[query[i].se] = pf[1][i] * query[i].fi + pf[0][i];
    }
    for (ll i = 1;i <= q;i ++){
        cout<<ans[i]<<'\n';
    }
}

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