Submission #1077596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077596		vjudge1	Phone Plans (CCO22_day2problem2)	C++17	0 / 25	729 ms	72772 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+5;
const ll offset=2e5;
const ll inf=1e18;
const int base=350;
const ll mod=998244353;
int n,q,a,b,k;

struct Edge
{
    int u,v,w;
    bool operator <(const Edge& o) const
    {
        return w<o.w;
    }
}ea[maxn],eb[maxn];
struct Event
{
    int u,v,v1;
};
int par[2][maxn];
vector<int> L[2][maxn];
vector<Event> trace[maxn];
int Find(int id,int u)
{
    return par[id][u]<0?u:par[id][u]=Find(id,par[id][u]);
}
int cur=0,ans=inf;
map<pii,int> cnt;

int Get(int u) {return u*(u-1)/2;}
void Update(int u,int val)
{
    cur+=Get(cnt[{Find(0,u),Find(1,u)}]);
    cnt[{Find(0,u),Find(1,u)}]+=val;
    cur-=Get(cnt[{Find(0,u),Find(1,u)}]);
//    cerr<<"Add "<<u<<' '<< Find(0,u) <<' '<<Find(1,u)<<' '<<val<<'\n';
}
void Union(int id,int u,int v,int idd)
{
    if ((u=Find(id,u))==(v=Find(id,v))) return;
//    cerr<< "Merge "<<id<<' '<<u<<' '<<v<<'\n';
    if (par[id][u]>par[id][v]) swap(u,v);
    cur-=Get(-par[id][u]);
    cur-=Get(-par[id][v]);
    par[id][u]+=par[id][v];
//        if (id==1) cerr<< "trace "<<idd<<' '<<u<<' '<<par[id][4]<<' '<<4<<'\n';

    for(int v1:L[id][v])
    {
        if (v1==v) continue;
        L[id][u].pb(v1);
        Update(v1,-1);
//        if (id==1) cerr<< "trace "<<idd<<' '<<u<<' '<<par[id][v1]<<' '<<v1<<'\n';
        if (id==1)
        {
            trace[idd].pb({u,par[id][v1],v1});
        }
        par[id][v1]=u;
        Update(v1,1);
    }
    L[id][u].pb(v);
    Update(v,-1);
    if (id==1)
    {
        trace[idd].pb({u,par[id][v],v});
    }
    par[id][v]=u;
    Update(v,1);
    cur+=Get(-par[id][u]);
    L[id][v].clear();
}
void clear()
{
    cur=0;
    cnt.clear();
    for1(id,0,1) for1(i,1,n)
    {
        par[id][i]=-1;
        L[id][i].clear();
        L[id][i].pb(i);
    }
    for1(i,1,n) Update(i,1);
}
int pre[2][maxn];
void sol()
{
    cin >> n>>a>>b>>k;
    for1(i,1,a) cin >> ea[i].u>> ea[i].v>>ea[i].w;
    for1(i,1,b) cin >> eb[i].u>> eb[i].v>>eb[i].w;
    sort(ea+1,ea+1+a);
    sort(eb+1,eb+1+b);
    clear();
    for1(i,1,a)
    {

        Union(0,ea[i].u,ea[i].v,i);

        if (cur>=k)
        {
            ans=min(ans,ea[i].w);
            break;
        }
    }
//    cerr<< "reset:\n";
    clear();
    for1(i,1,b)
    {
//        cerr<< "Merge "<<"1 "<<eb[i].u<<' '<<eb[i].v<<'\n';
        Union(1,eb[i].u,eb[i].v,i);
//        if (i==2)
//        {
//            for(auto x: L[1][1])
//            {
//                cerr<<"gg "<< x<<'\n';
//            }
//        }
        for(Event& x:trace[i])
        {
            if (x.v<0) swap(x,trace[i].back());
        }
        if (cur>=k)
        {
            ans=min(ans,eb[i].w);
            break;
        }
    }
//        cerr<< cur<<'\n';
    int j=b;
    for1(i,1,a)
    {
//        cerr<< "Merge "<<"0 "<<ea[i].u<<' '<<ea[i].v<<'\n';
        Union(0,ea[i].u,ea[i].v,i);
//        cerr<< i<<' '<<cur<<'\n';
//        if (cur<k) continue;
//        for1(i,1,n) cerr<<"gg "<< Find(0,i)<<' '<<Find(1,i)<<'\n';
//        cerr<< i<<' '<<j<<' '<<cur<<'\n';
        while (cur>=k && j>=1)
        {
//            cerr<< "Rollback "<<"1 "<<eb[j].u<<' '<<eb[j].v<<'\n';
            for(Event x:trace[j])
            {
                int u=x.u,v=x.v,v1=x.v1;
                Update(v1,-1);
                par[1][v1]=v;
//                cerr<< v1<<" -> "<<v<<'\n';
                if (v<0)
                {
                    cur+=Get(-par[1][v1]);
                    cur-=Get(-par[1][u]);
                    par[1][u]-=v;
                    cur+=Get(-par[1][u]);
                }
            }
            for(Event x:trace[j]) Update(x.v1,1);
            j--;
        }
//        for1(i,1,n) cerr<<"gg "<< Find(0,i)<<' '<<Find(1,i)<<'\n';
//        cerr<< i<<' '<<j<<' '<<cur<<'\n';
//        if (cur>=k) ans=min(ans,pre[1][i]);
        if (j<b) ans=min(ans,ea[i].w+eb[j+1].w);
    }
    if (ans!=inf) cout << ans;
    else cout << -1;

}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("propagation.inp","r",stdin);
//    freopen("propagation.out","w",stdout);
    int t=1;//cin >> t;
    while (t--) {
        sol();
    }
}

/*
6 7 2 7
4 6 2
3 5 3
3 3 2
5 6 6
4 6 2
1 1 1
3 3 7
1 5 48
5 6 10


5 2 5 5
2 5 6
1 5 8
1 1 11
1 4 42
3 4 47
2 4 38
3 5 36




*/

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