Submission #907324

#	Time	Username	Problem	Language	Result	Execution time	Memory
907324		Tuanlinh123	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	2531 ms	50880 KiB

reconstruction

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=505, maxm=100005, maxq=1000005;
pair<ll, pll> e[maxm];
vector <pair<pll, ll>> edge;
ll n, m, x[maxq], ans[maxq], cnt[maxq];

struct DSU
{
    vector <ll> pa, Rank;
    DSU(ll n)
    {
        pa.assign(n+1, 0);
        for (ll i=1; i<=n; i++)
            pa[i]=i;
        Rank.assign(n+1, 0);
    }
    
    ll Find(ll i)
    {
        if (pa[i]!=i)
            pa[i]=Find(pa[i]);
        return pa[i];
    }

    bool Union(ll a, ll b)
    {
        ll Pa=Find(a), Pb=Find(b);
        if (Pa==Pb) return 0;
        if (Rank[Pa]<Rank[Pb]) swap(Pa, Pb);
        if (Rank[Pa]==Rank[Pb]) Rank[Pa]++;
        pa[Pb]=Pa; return 1;
    }
};


void addedge(ll u, ll v, ll id)
{
    DSU A(n);
    vector <pair<pll, ll>> edgen;
    edgen.pb({{u, v}, id}); A.Union(u, v);
    for (pair<pll, ll> e:edge)
        if (A.Union(e.fi.fi, e.fi.se))
            edgen.pb(e);
    swap(edge, edgen);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (ll i=1; i<=m; i++)
        cin >> e[i].se.fi >> e[i].se.se >> e[i].fi;
    sort(e+1, e+m+1);
    ll q; cin >> q;
    for (ll i=1; i<=q; i++)
        cin >> x[i];
    for (ll i=1; i<=m; i++)
    {
        DSU A(n);
        ll u=e[i].se.fi, v=e[i].se.se, w=e[i].fi, ok=0;
        for (pair<pll, ll> j:edge)
        {
            A.Union(j.fi.fi, j.fi.se);
            if (A.Find(u)==A.Find(v))
                {ok=e[j.se].fi; break;}
        }
        ll p=upper_bound(x+1, x+q+1, w)-x;
        if (!ok) ans[1]+=w, ans[p]-=w, cnt[1]--, cnt[p]++;
        else
        {
            ll L=(ok+w)/2+1, p1=lower_bound(x+1, x+q+1, L)-x;
            ans[p1]+=w, ans[p]-=w, cnt[p1]--, cnt[p]++;
        }
        addedge(u, v, i);
    }
    edge.clear();
    for (ll i=m; i>=1; i--)
    {
        DSU A(n);
        ll u=e[i].se.fi, v=e[i].se.se, w=e[i].fi, ok=0;
        for (pair<pll, ll> j:edge)
        {
            A.Union(j.fi.fi, j.fi.se);
            if (A.Find(u)==A.Find(v))
                {ok=e[j.se].fi; break;}
        }
        ll p=upper_bound(x+1, x+q+1, w)-x;
        if (!ok) ans[p]-=w, cnt[p]++;
        else
        {
            ll R=(ok+w)/2, p1=upper_bound(x+1, x+q+1, R)-x;
            ans[p]-=w, ans[p1]+=w, cnt[p]++, cnt[p1]--;
        }
        addedge(u, v, i);
    }
    for (ll i=1; i<=q; i++)
    {
        ans[i]+=ans[i-1], cnt[i]+=cnt[i-1];
        cout << ans[i]+cnt[i]*x[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