Submission #1073925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073925		DucNguyen2007	Phone Plans (CCO22_day2problem2)	C++14	6 / 25	717 ms	85992 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=2e5+5;
const ll inf=2e18;
int n,A,B,k,pa[maxN+1],par[maxN+1];
ll ca[maxN+1],cb[maxN+1];
map<pii,int> mp;
struct canh
{
    int u,v;
    ll w;
};
struct node
{
    int u,pre,cur;
};
vector<node> vec_a[maxN+1],vec_b[maxN+1];
canh a[maxN+1],b[maxN+1];
struct dsu
{
    int parent[maxN+1];
    ll cnt;
    vector<int> vec[maxN+1];
    dsu()
    {
        memset(parent,-1,sizeof(parent));
        for(int i=1;i<=n;i++)
        {
            vec[i].clear();
        }
        cnt=0;
    }
    void clr()
    {
        memset(parent,-1,sizeof(parent));
        for(int i=1;i<=n;i++)
        {
            vec[i].clear();
        }
        cnt=0;
    }
    int Find(int v)
    {
        if(parent[v]<0)
        {
            return v;
        }
        return parent[v]=Find(parent[v]);
    }
    vector<node> Union(int a,int b)
    {
        a=Find(a);
        b=Find(b);
        vector<node> vt;
        if(a==b)
        {
            return vt;
        }
        if(-parent[a]<-parent[b])
        {
            swap(a,b);
        }
        cnt+=(parent[a]*parent[b]);
        parent[a]+=parent[b];
        parent[b]=a;
        //cout<<vec[a].size()<<" "<<vec[b].size()<<" ";
        for(auto i:vec[b])
        {
            vec[a].push_back(i);
            vt.push_back({i,b,a});
        }
        return vt;
    }
}ds;
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>A>>B>>k;
    for(int i=1;i<=A;i++)
    {
        cin>>a[i].u>>a[i].v>>a[i].w;
    }
    sort(a+1,a+A+1,[&](canh x,canh y)
    {
        return x.w<y.w;
    });
    for(int i=1;i<=B;i++)
    {
        cin>>b[i].u>>b[i].v>>b[i].w;
    }
    sort(b+1,b+B+1,[&](canh x,canh y)
    {
        return x.w<y.w;
    });
    if(k==0)
    {
        cout<<0;
        return 0;
    }
    ll ans=inf;
    for(int i=1;i<=n;i++)
    {
        ds.vec[i].push_back(i);
    }
    for(int i=1;i<=A;i++)
    {
        //cout<<a[i].u<<" "<<a[i].v<<" "<<a[i].w<<'\n';
        vec_a[i]=ds.Union(a[i].u,a[i].v);
        ca[i]=ds.cnt;
        if(ca[i]>=k)
        {
            ans=min(ans,a[i].w);
        }
    }
    ds.clr();
    for(int i=1;i<=n;i++)
    {
        ds.vec[i].push_back(i);
    }
    for(int i=1;i<=B;i++)
    {
        vec_b[i]=ds.Union(b[i].u,b[i].v);
        cb[i]=ds.cnt;
        if(cb[i]>=k)
        {
            ans=min(ans,b[i].w);
        }
    }
    for(int i=1;i<=n;i++)
    {
        pa[i]=i;
        par[i]=ds.Find(i);
        mp[{pa[i],par[i]}]++;
    }
    ll ch=0;
    for(int i=1,j=B;i<=A;i++)
    {
        for(auto [u,pre,cur]:vec_a[i])
        {
            mp[{pa[u],par[u]}]--;
            ch-=mp[{pa[u],par[u]}];
            pa[u]=cur;
            ch+=mp[{pa[u],par[u]}];
            mp[{pa[u],par[u]}]++;
        }
        while(j>=0&&ca[i]+cb[j]-ch>=k)
        {
            for(auto [u,pre,cur]:vec_b[j])
            {
                mp[{pa[u],par[u]}]--;
                ch-=mp[{pa[u],par[u]}];
                par[u]=pre;
                ch+=mp[{pa[u],par[u]}];
                mp[{pa[u],par[u]}]++;
            }
            j--;
        }
        if(j!=B)
        {
            //cout<<i<<" "<<j<<" "<<ch<<'\n';
            ans=min(ans,a[i].w+b[j+1].w);
        }
    }
    if(ans==inf)
    {
        cout<<-1;
    }
    else cout<<ans;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:147:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  147 |         for(auto [u,pre,cur]:vec_a[i])
      |                  ^
Main.cpp:157:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  157 |             for(auto [u,pre,cur]:vec_b[j])
      |                      ^

• Subtask 1: 6 / 6
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 8