Submission #693973

#	Time	Username	Problem	Language	Result	Execution time	Memory
693973		safaricola	Phone Plans (CCO22_day2problem2)	C++17	0 / 25	181 ms	60836 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define rep(i,n) for(ll i = 1; i <= n; i++)
ll n,na,nb,k,w,sum,p[200010],ngs[200010];
pair<ll,ii> d[200010], dd[200010];
vector<ll> adj[200010],adjl[200010];
set<ll> s,ss;
map<ll,ll> m,mm;
ll find(ll x){
    ll ind= *upper_bound(s.begin(), s.end(), x);
    return m[ind];
}
ll par(ll x) { return (p[x]==x)? x:p[x]=par(p[x]); }

//p[par(a)] = par(b)

bool check(ll L){
    ll bb=nb;
    ll ma=0;
    rep(i, na){
        if(L<=d[i].f){
            break;
        }
        while(dd[bb].f>L-m[d[i].f]){ // dd is the level
            assert(bb>=0);
            bb--;
        }
        //cout<<i<<' '<<dd[bb].f<<' '<<mm[dd[bb].f]<<' '<<d[i].f<<' '<<m[d[i].f]<<endl;
        ma=max(mm[dd[bb].f]+m[d[i].f], ma);
    }
    //cout<<L<<' '<<ma<<endl;
    return ma<k;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>na>>nb>>k;
    rep(i,n) p[i] = i;
    rep(i,n) ngs[i]=1;
    rep(i,na){
        cin>>d[i].s.f>>d[i].s.s>>d[i].f;
    }
    sort(d+1, d+na+1);
    rep(i,na){
        //cout<<d[i].f<<' ';
        if(par(d[i].s.s)==par(d[i].s.f)){
            m[d[i].f]=m[d[i-1].f]; 
            continue;
        }
        ll init=ngs[par(d[i].s.s)]*(ngs[par(d[i].s.s)]-1)/2+ngs[par(d[i].s.f)]*(ngs[par(d[i].s.f)]-1)/2;
        ll nogrps= ngs[par(d[i].s.s)]+ngs[par(d[i].s.f)];
        p[par(d[i].s.s)] = par(d[i].s.f);
        ngs[par(d[i].s.s)] = nogrps;
        sum+=nogrps*(nogrps-1)/2-init;
        m[d[i].f]=sum;
        //cout<<sum<<endl;
    }
    rep(i,nb){
        cin>>dd[i].s.f>>dd[i].s.s>>dd[i].f;
    }
    rep(i,n) p[i] = i;
    rep(i,n) ngs[i]=1;
    sort(dd+1, dd+nb+1);
    sum=0;
    rep(i,nb){
        //cout<<dd[i].f<<' ';
        if(par(dd[i].s.s)==par(dd[i].s.f)){
            mm[dd[i].f]=mm[dd[i-1].f]; 
            continue;
        }
        ll init=ngs[par(dd[i].s.s)]*(ngs[par(dd[i].s.s)]-1)/2+ngs[par(dd[i].s.f)]*(ngs[par(dd[i].s.f)]-1)/2;
        ll nogrps= ngs[par(dd[i].s.s)]+ngs[par(dd[i].s.f)];
        p[par(dd[i].s.s)] = par(dd[i].s.f);
        ngs[par(dd[i].s.s)] = nogrps;
        sum+=nogrps*(nogrps-1)/2-init;
        mm[dd[i].f]=sum;
        //cout<<sum<<endl;
    }
    ll maxn=d[na].f+dd[nb].f;
    ll s=-1, e=maxn, mid;
    while(mid=(e+s)/2, e-s>1){
        if(check(mid)) s=mid;
        else e=mid;
    }
    cout<<e;
}

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