oj.uz

Submission #1076645

# Submission time Handle Problem Language Result Execution time Memory
1076645 2024-08-26T15:13:56 Z giaminh2211 Phone Plans (CCO22_day2problem2) C++14
0 / 25
 94 ms 34900 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Runtime error 15 ms 31620 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 34900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 27740 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Runtime error 15 ms 31620 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -