Submission #874171

#	Time	Username	Problem	Language	Result	Execution time	Memory
874171		vjudge1	Reconstruction Project (JOI22_reconstruction)	C++14	0 / 100	738 ms	1048576 KiB

reconstruction

#include<bits/stdc++.h>
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=1e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll lab[maxn];
ll u[maxn],v[maxn],w[maxn];
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
bool unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(u==v) return false;
    if(lab[u]>lab[v]) swap(u,v);
    lab[u]+=lab[v];
    lab[v]=u;
    return true;
}
ll n,m,q;
struct edge
{
    ll u,v,w,id;
    bool operator<(const edge&o)
    {
        return w<o.w;
    }
}e[maxn];
ll cac[maxn];
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].id=i;
        u[i]=e[i].u;
        v[i]=e[i].v;
        w[i]=e[i].w;
    }
    sort(e+1,e+m+1);
    vector<ll>c,d,tt;
    for(int i=m;i>=1;i--)
    {
        tt.clear();
        cac[i]=0;
        d.insert(d.begin(),e[i].id);
        for(int j=1;j<=m;j++) lab[j]=-1;
        for(int j=0;j<d.size();j++)
        {
            if(unite(u[d[j]],v[d[j]])) tt.pb(d[j]);
            else
            {
                cac[i]=d[j];
            }
        }
        tt.swap(d);
    }
    ll o=1;
    cin >> q;
    while(q--)
    {
        ll x;
        cin >> x;
        while(o<=m&&e[o].w<=x)
        {
            for(int i=1;i<=n;i++) lab[i]=-1;
            c.insert(c.begin(),e[o].id);
            tt.clear();
            for(int j=0;j<c.size();j++)
            {
                if(unite(u[c[j]],v[c[j]])) tt.pb(c[j]);
            }
            c.swap(tt);
            tt.clear();
            if(d.size()) d.erase(d.begin());
            if(cac[o]!=0)
            {
                bool ins=false;
                for(int j=0;j<d.size();j++)
                {
                    if(w[d[j]]>=w[cac[o]]&&ins==false)
                    {
                        ins=true;
                        tt.pb(cac[o]);
                    }
                    tt.pb(d[j]);
                }
                if(ins==false) tt.pb(cac[o]);
                d.swap(tt);
            }
            o++;
        }
        for(int i=1;i<=n;i++) lab[i]=-1;
        ll j=0,k=0,ans=0;
        while(-lab[findset(1)]!=n)
        {
            if(j==c.size()&&k==d.size()) break;
            if(j==c.size())
            {
                ans+=unite(u[d[k]],v[d[k]])*abs(w[d[k]]-x);
                k++;
                continue;
            }
            if(k==d.size())
            {
                ans+=unite(u[c[j]],v[c[j]])*abs(w[c[j]]-x);
                j++;
                continue;
            }
            ll cost1=abs(w[c[j]]-x);
            ll cost2=abs(w[d[k]]-x);
            if(cost1<cost2)
            {
                ans+=unite(u[c[j]],v[c[j]])*abs(w[c[j]]-x);
                j++;
            }
            else
            {
                ans+=unite(u[d[k]],v[d[k]])*abs(w[d[k]]-x);
                k++;
            }
        }
        cout << ans << '\n';
    }
}
int main()
{
    fastio
    //freopen("c.INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

reconstruction.cpp: In function 'void solve()':
reconstruction.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0;j<d.size();j++)
      |                     ~^~~~~~~~~
reconstruction.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for(int j=0;j<c.size();j++)
      |                         ~^~~~~~~~~
reconstruction.cpp:88:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                 for(int j=0;j<d.size();j++)
      |                             ~^~~~~~~~~
reconstruction.cpp:106:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             if(j==c.size()&&k==d.size()) break;
      |                ~^~~~~~~~~~
reconstruction.cpp:106:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             if(j==c.size()&&k==d.size()) break;
      |                             ~^~~~~~~~~~
reconstruction.cpp:107:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             if(j==c.size())
      |                ~^~~~~~~~~~
reconstruction.cpp:113:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             if(k==d.size())
      |                ~^~~~~~~~~~

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