Submission #938888

#	Time	Username	Problem	Language	Result	Execution time	Memory
938888		andrei_boaca	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1767 ms	38828 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF=1e9;
ll n,m;
struct date
{
    ll a,b,c;
} v[100005];
struct ev
{
    ll poz,c1,c0;
};
vector<ev> events;
bool comp(date a, date b)
{
    return a.c<b.c;
}
bool bypoz(ev a, ev b)
{
    return a.poz<b.poz;
}
ll par[505],sz[505];
ll getpar(ll a)
{
    if(a==par[a])
        return a;
    par[a]=getpar(par[a]);
    return par[a];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        v[i]={a,b,c};
    }
    sort(v+1,v+m+1,comp);
    for(int i=1;i<=m;i++)
    {
        bool ok=0;
        if(i==3)
            ok=1;
        for(int j=1;j<=n;j++)
        {
            par[j]=j;
            sz[j]=1;
        }
        int nrcomp=n;
        int j=i-1;
        while(j>0)
        {
            int a=getpar(v[j].a);
            int b=getpar(v[j].b);
            if(a!=b)
            {
                if(sz[a]<sz[b])
                    swap(a,b);
                par[a]=b;
                sz[a]+=sz[b];
                nrcomp--;
                if(getpar(v[i].a)==getpar(v[i].b))
                    break;
            }
            j--;
        }
        if(j==0)
        {
            events.push_back({1,-1,v[i].c});
            events.push_back({v[i].c+1,1,-v[i].c});
        }
        else
        {
            ll poz=(v[i].c+v[j].c)/2;
            while(poz-v[j].c<=v[i].c-poz)
                poz++;
            events.push_back({poz,-1,v[i].c});
            events.push_back({v[i].c+1,1,-v[i].c});
        }
    }
    for(int i=m;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
        {
            par[j]=j;
            sz[j]=1;
        }
        int nrcomp=n;
        int j=i+1;
        while(j<=m)
        {
            int a=getpar(v[j].a);
            int b=getpar(v[j].b);
            if(a!=b)
            {
                if(sz[a]<sz[b])
                    swap(a,b);
                par[a]=b;
                sz[a]+=sz[b];
                nrcomp--;
                if(getpar(v[i].a)==getpar(v[i].b))
                    break;
            }
            j++;
        }
        if(j==m+1)
        {
            events.push_back({v[i].c+1,1,-v[i].c});
            events.push_back({INF+1,-1,v[i].c});
        }
        else
        {
            ll poz=(v[i].c+v[j].c)/2;
            while(poz-v[i].c>v[j].c-poz)
                poz--;
            events.push_back({v[i].c+1,1,-v[i].c});
            events.push_back({poz+1,-1,v[i].c});
        }
    }
    sort(events.begin(),events.end(),bypoz);
    reverse(events.begin(),events.end());
    ll c0=0,c1=0;
    ll q;
    cin>>q;
    while(q--)
    {
        ll x;
        cin>>x;
        while(!events.empty()&&events.back().poz<=x)
        {
            c0+=events.back().c0;
            c1+=events.back().c1;
            events.pop_back();
        }
        ll ans=c1*x+c0;
        cout<<ans<<'\n';
    }
    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:46:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   46 |         bool ok=0;
      |              ^~

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