Submission #1076645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076645		giaminh2211	Phone Plans (CCO22_day2problem2)	C++14	0 / 25	94 ms	34900 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using node=tuple<int, int, int, int, int, int, int>;

const int N=2e5+13;
ll ans;
stack<node> roll;
map<int, int> h[N];

struct DSU{
    int par[N];
    int sz[N];

    void init(int sus){
        for(int i=1; i<=sus; i++){
            par[i]=i;
            sz[i]=1;
        }
    }

    int f(int v){
        if(par[v]==v) return v;
        return f(par[v]);
    }

    void uni(int x, int y){
        int Ru=f(x);
        int Rv=f(y);
        if(Ru!=Rv){
            if(sz[Ru] < sz[Rv]) swap(Ru, Rv);
            roll.push({Ru, Rv, ans, sz[Ru], sz[Rv], par[Ru], par[Rv]});
            ans -= sz[Ru] * (sz[Ru]-1)/2;
            ans -= sz[Rv] * (sz[Rv]-1)/2;
            par[Rv]=Ru;
            sz[Ru] += sz[Rv];
            ans += sz[Ru] * (sz[Ru]-1)/2;
        }
        else roll.push({-1, -1, -1, -1, -1, -1, -1});
    }

    void rollback(){
        node tmp=roll.top();
        roll.pop();
        int x=get<0>(tmp);
        int y=get<1>(tmp);
        if(x==-1) return;
        //cerr << sz[x] << '\n';
        ans -= sz[x]*(sz[x]-1)/2;
        //cerr << ans << '\n';
        sz[x]=get<3>(tmp);
        sz[y]=get<4>(tmp);
        ans += sz[x]*(sz[x]-1)/2;
        ans += sz[y]*(sz[y]-1)/2;
        //cerr << ans << '\n';
        par[x]=get<5>(tmp);
        par[y]=get<6>(tmp);
        //cerr << ans << '\n';
    }
};

struct E{
    int x, y;
    ll w;

    bool operator < (const E& o) const{
        return w < o.w;
    }
};

int k, n, m, p;
E a[N];
E b[N];
int op[N];
ll res=1e18;
DSU dsu_a, dsu_b;

void scan(){
    cin >> p >> n >> m >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i].x >> a[i].y >> a[i].w;
    }
    for(int i=1; i<=m; i++){
        cin >> b[i].x >> b[i].y >> b[i].w;
    }
    sort(a+1, a+n+1);
    sort(b+1, b+m+1);
    dsu_a.init(p);
    dsu_b.init(p);
    for(int i=1; i<=m; i++){
        dsu_b.uni(b[i].x, b[i].y);
        /*for(int i=1; i<=p; i++){
        	cout << dsu_b.par[i] << ' ';
        }
        cout << '\n';*/
    }
    for(int i=1; i<=p; i++){
        h[i][dsu_b.par[i]]++;
    }
}

inline ll sus(ll val){
    return val*(val-1)/2;
}

void add(int x, int y){
	ans -= sus(h[dsu_a.f(x)][dsu_b.f(x)]);
	ans -= sus(h[dsu_a.f(y)][dsu_b.f(y)]);
	h[dsu_a.f(x)][dsu_b.f(x)]--;
	h[dsu_a.f(y)][dsu_b.f(y)]--;
	dsu_a.uni(x, y);
	h[dsu_a.f(x)][dsu_b.f(x)]+=2;
	ans += sus(h[dsu_a.f(x)][dsu_b.f(x)]);
}

void rollback(int x, int y){
	ans -= sus(h[dsu_a.f(x)][dsu_b.f(x)]);
	h[dsu_a.f(x)][dsu_b.f(x)]-=2;
	dsu_b.rollback();
	//cerr << ans << '\n';
	ans += sus(h[dsu_a.f(x)][dsu_b.f(x)]);
	ans += sus(h[dsu_a.f(y)][dsu_b.f(y)]);
	h[dsu_a.f(x)][dsu_b.f(x)]++;
	h[dsu_a.f(y)][dsu_b.f(y)]++;
}

void solve(){
    int i=1;
    while(i<=n && ans < k){
    	add(a[i].x, a[i].y);
    }
    if(ans>=k) res=min(res, b[m].w + a[i-1].w);
    for(int j=m-1; j>=m-1; j--){
    	rollback(b[j+1].x, b[j+1].y);
        while(i<=n && ans < k){
            add(a[i].x, a[i].y);
            ++i;
        }
        if(ans>=k) res=min(res, b[j].w + a[i-1].w);
        
    }
    cout << res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

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