Submission #733958

#	Time	Username	Problem	Language	Result	Execution time	Memory
733958		loctildore	Phone Plans (CCO22_day2problem2)	C++17	25 / 25	959 ms	131904 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
int n, ca, cb, k;
int u, v, l;
int ans = INT_MAX;
vector<tuple<int,int,int>> va, vb;
vector<pair<int,pair<int,int>>> lga[200069], lgb[200069];
int cnt, cnta[200069], cntb[200069];
vector<int> chd[200069];
int par[200069];
pair<int,int> rts[200069];
map<int,int> mp[200069];
void dsuclr() {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        chd[i].clear();
        chd[i].push_back(i);
    }
    cnt = 0;
}
void merge(int x, int y, vector<pair<int,pair<int,int>>> &lg) {
    x = par[x]; y = par[y];
    if (x == y) return;
    if (chd[x].size() < chd[y].size()) swap(x, y);
    cnt += chd[x].size() * chd[y].size();
    for (auto i : chd[y]) {
        par[i] = x;
        chd[x].push_back(i);
        lg.push_back({i, {y, x}});
    }
    chd[y].clear();
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>n>>ca>>cb>>k;
    dsuclr();
    for (int i = 0; i < ca; i++) {
        cin>>u>>v>>l; u--; v--;
        va.push_back({l, u, v});
    }
    sort(all(va));
    for (int i = 0; i < ca; i++) {
        tie(l, u, v) = va[i];
        merge(u, v, lga[i + 1]);
        cnta[i + 1] = cnt;
    }
    for (int i = 0; i < n; i++) {
        rts[i] = {par[i], i};
        mp[par[i]][i] = 1;
    }
    dsuclr();
    for (int i = 0; i < cb; i++) {
        cin>>u>>v>>l; u--; v--;
        vb.push_back({l, u, v});
    }
    sort(all(vb));
    for (int i = 0; i < cb; i++) {
        tie(l, u, v) = vb[i];
        merge(u, v, lgb[i + 1]);
        cntb[i + 1] = cnt;
    }
    cnt = 0;
    int tb = 0;
    for (int ta = ca; ~ta; ta--) {
        for (auto t : lga[ta + 1]) {
            int i = t.f;
            mp[rts[i].f][rts[i].s]--;
            cnt-=mp[rts[i].f][rts[i].s];
            rts[i].f = t.s.f;
            cnt+=mp[rts[i].f][rts[i].s];
            mp[rts[i].f][rts[i].s]++;
        }
        while (tb < cb && cnta[ta] + cntb[tb] - cnt < k) {
            for (auto t : lgb[tb + 1]) {
                int i = t.f;
                mp[rts[i].f][rts[i].s]--;
                cnt-=mp[rts[i].f][rts[i].s];
                rts[i].s = t.s.s;
                cnt+=mp[rts[i].f][rts[i].s];
                mp[rts[i].f][rts[i].s]++;
            }
            tb++;
        }
        if (cnta[ta] + cntb[tb] - cnt >= k) {
            int tmpa = (ta == 0 ? 0 : get<0>(va[ta - 1]));
            int tmpb = (tb == 0 ? 0 : get<0>(vb[tb - 1]));
            ans = min(ans, tmpa + tmpb);
        }
    }
    cout<<(ans == INT_MAX ? -1 : ans)<<endl;
    return 0;
}

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