Submission #873698

#	Time	Username	Problem	Language	Result	Execution time	Memory
873698		vjudge1	Reconstruction Project (JOI22_reconstruction)	C++17	7 / 100	5074 ms	8852 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=2e5;
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;
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> u[i] >> v[i] >> w[i];
    }
    cin >> q;
    while(q--)
    {
        ll x;
        cin >> x;
        vector<pli>a,b;
        for(int j=1;j<=m;j++)
        {
            if(w[j]<=x)
            {
                a.pb({x-w[j],j});
            }
            else
            {
                b.pb({w[j]-x,j});
            }
        }
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        vector<ll>c,d;
        for(int i=1;i<=n;i++) lab[i]=-1;
        for(int j=0;j<a.size();j++)
        {
            ll id=a[j].se;
            if(unite(u[id],v[id])) c.pb(id);
        }
        for(int i=1;i<=n;i++) lab[i]=-1;
        for(int j=0;j<b.size();j++)
        {
            ll id=b[j].se;
            if(unite(u[id],v[id])) d.pb(id);
        }
        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())
            {
                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(TASKNAME".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<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0;j<a.size();j++)
      |                     ~^~~~~~~~~
reconstruction.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j=0;j<b.size();j++)
      |                     ~^~~~~~~~~
reconstruction.cpp:72: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]
   72 |             if(j==c.size())
      |                ~^~~~~~~~~~
reconstruction.cpp:78: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]
   78 |             if(k==d.size())
      |                ~^~~~~~~~~~

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