Submission #1073063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073063		MOUF_MAHMALAT	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	663 ms	27840 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;
const ll inf=1e9+9;
struct node
{
    ll a,b,c;
} a[oo];
bool cmp(const node&A,const node&B)
{
    return A.c < B.c;
}
ll n,m,p[509],q;
bool vis[oo];
vector<ll>lst;
vector<pll>v;
ll gp(ll z)
{
    if(p[z]<0)
        return z;
    return p[z]=gp(p[z]);
}
bool mrg(ll x,ll y)
{
    x=gp(x),y=gp(y);
    if(x==y)
        return 0;
    if(p[x]>p[y])
        swap(x,y);
    p[x]+=p[y];
    p[y]=x;
    return 1;
}
void solve()
{
    cin>>n>>m;
    for(ll i=0; i<m; i++)
        cin>>a[i].a>>a[i].b>>a[i].c;
    sort(a,a+m,cmp);
//    for(ll i=0; i<m; i++)
//        cout<<a[i].a<<" "<<a[i].b<<" "<<a[i].c<<"\n";
    for(ll i=0; i<m; i++)
    {
        for(ll j=1; j<=n; j++)
            p[j]=-1;
        lst.push_back(i);
        ll id=-1;
        for(ll j=(ll)lst.size()-1; j>=0; j--)
        {
            ll x=lst[j];
            if(!mrg(a[x].a,a[x].b))
            {
                id=j;
                break;
            }
        }
        if(id!=-1)
        {
            ll x=lst[id];
//            cout<<x<<" <- "<<i<<"\n";
            vis[x]=1;
            v.push_back({(a[x].c+a[i].c)/2+1,x});
            lst.erase(lst.begin()+id);
        }
    }
    for(ll i=0; i<m; i++)
        if(!vis[i])
            v.push_back({inf,i});
    memset(vis,0,sizeof vis);
    lst.clear();
    for(ll i=m-1; i>=0; i--)
    {
        for(ll j=1; j<=n; j++)
            p[j]=-1;
        lst.push_back(i);
        ll id=-1;
        for(ll j=(ll)lst.size()-1; j>=0; j--)
        {
            ll x=lst[j];
            if(!mrg(a[x].a,a[x].b))
            {
                id=j;
                break;
            }
        }
        if(id!=-1)
        {
            ll x=lst[id];
//            cout<<i<<" -> "<<x<<"\n";
            vis[x]=1;
            v.push_back({(a[x].c+a[i].c)/2+1,x});
            lst.erase(lst.begin()+id);
        }
    }
    for(ll i=0; i<m; i++)
        if(!vis[i])
            v.push_back({0,i});
    sort(all(v));
//    for(auto&z:v)
//        cout<<z.F<<" "<<z.S<<"\n";
    memset(vis,0,sizeof vis);
    cin>>q;
    ll le=0,cl=0,cr=0;
    long long suml=0,sumr=0;
    multiset<ll>s;
    while(q--)
    {
        ll x;
        cin>>x;
        while(le<v.size()&&v[le].F<=x)
        {
            ll o=v[le].S;
            if(vis[o])
            {
                if(s.find(a[o].c)!=s.end())
                {
                    cl--,suml-=a[o].c;
                    s.erase(s.find(a[o].c));
                }
                else
                {
                    cr--,sumr-=a[o].c;
                }
            }
            else
            {
                vis[o]=1;
                cl++,suml+=a[o].c;
                s.insert(a[o].c);
            }
            le++;

//        cout<<suml<<" "<<sumr<<" "<<cl<<" "<<cr<<"\n";
        }
        while(!s.empty()&&*s.begin()<x)
        {
            cl--,suml-=*s.begin();
            cr++,sumr+=*s.begin();
            s.erase(s.begin());
        }
//        cout<<suml<<" "<<sumr<<" "<<cl<<" "<<cr<<"\n";
        cout<<suml-sumr-1ll*cl*x+1ll*cr*x<<"\n";
    }
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    ll tt=1;
//    cin>>tt;
    while(tt--)
        solve();
    return 0;
}

Compilation message (stderr)

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

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