Submission #1072412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072412		MOUF_MAHMALAT	Reconstruction Project (JOI22_reconstruction)	C++14	42 / 100	5074 ms	210280 KiB

reconstruction

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define F first
#define S second
using namespace std;
typedef int ll;
typedef pair<ll,ll>pll;
const ll oo=1e5+9;
ll n,m,par[509],sz[509],q;
vector<pair<ll,pll>>v;
vector<ll>r[oo],lst;
ll gp(ll z)
{
    if(par[z]==z)
        return z;
    return par[z]=gp(par[z]);
}
bool mrg(ll x,ll y)
{
    x=gp(x),y=gp(y);
    if(x==y)
        return 0;
    if(sz[x]<sz[y])
        swap(x,y);
    par[y]=x;
    sz[x]+=sz[y];
    return 1;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(ll i=0; i<m; i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;
        v.push_back({z,{x,y}});
    }
    sort(all(v));
    for(ll i=m-1; i>=0; i--)
    {
        for(ll j=1; j<=n; j++)
            par[j]=j,sz[j]=1;
        ll id=-1;
        lst.push_back(i);
        for(ll j=(ll)lst.size()-1; j>=0; j--)
        {
            if(!mrg(v[lst[j]].S.F,v[lst[j]].S.S))
            {
                id=j;
                break;
            }
        }
        if(id!=-1)
            lst.erase(lst.begin()+id);
        r[i]=lst;
//        for(auto&z:lst)
//            cout<<z<<"! ";
//        cout<<"\n";
    }
    lst.clear();
    ll le=0;
    cin>>q;
    while(q--)
    {
        ll x;
        cin>>x;
        while(le<v.size()&&v[le].F<=x)
        {
            for(ll i=1; i<=n; i++)
                par[i]=i,sz[i]=1;
            ll id=-1;
            lst.push_back(le);
            for(ll i=(ll)lst.size()-1; i>=0; i--)
            {
                if(!mrg(v[lst[i]].S.F,v[lst[i]].S.S))
                {
                    id=i;
                    break;
                }
            }
            if(id!=-1)
                lst.erase(lst.begin()+id);
            le++;
        }
        for(ll i=1;i<=n;i++)
            par[i]=i,sz[i]=1;
//        cout<<"?? ";
//        for(auto&z:lst)
//            cout<<z<<" ";
//        cout<<"\n";
//        cout<<le<<"????\n";
        long long ans=0;
        ll lx=(ll)lst.size()-1,rx=(ll)r[le].size()-1;
        while(lx>=0||rx>=0)
        {
//            cout<<lx<<" "<<rx<<"\n";
            if(rx==-1||(lx!=-1&&x-v[lst[lx]].F<v[r[le][rx]].F-x))
            {
//                cout<<v[lst[lx]].S.F<<" "<<v[lst[lx]].S.S<<"\n";
                if(mrg(v[lst[lx]].S.F,v[lst[lx]].S.S))
                    ans+=x-v[lst[lx]].F;
                lx--;
            }
            else
            {
//                cout<<v[r[le][rx]].S.F<<" "<<v[r[le][rx]].S.S<<"\n";
                if(mrg(v[r[le][rx]].S.F,v[r[le][rx]].S.S))
                    ans+=v[r[le][rx]].F-x;
                rx--;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:68:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while(le<v.size()&&v[le].F<=x)
      |               ~~^~~~~~~~~

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