Submission #1153312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153312		Math4Life2020	Swapping Cities (APIO20_swap)	C++20	100 / 100	568 ms	41944 KiB

swap

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
//implement persistent DSU

ll N1,M1;
const ll Nm = 1e5+5;
vector<int> W;
vector<pii> f[Nm]; //DSU forward
vector<pii> sz[Nm]; //DSU size
vector<pii> cd[Nm]; //DSU condition
ll deg[Nm]; //degree
//0 -> not OP, 1 -> OP


ll getf(ll x, ll wc) { //WRITE
    if (f[x].back().second==x) {
        return x;
    } else {
        ll y = getf(f[x].back().second,wc);
        // if (f[x].back().first==wc) {
        //     f[x].pop_back();
        // }
        // f[x].push_back({wc,y});
        return y;
    }
}


ll getfR(ll x, ll wc) { //READ
    auto A0 = lower_bound(f[x].begin(),f[x].end(),(pii){wc+1,-1});
    A0--;
    ll y = (*A0).second;
    if (x==y) {
        return x;
    } 
    return getfR(y,wc);
}

ll getCD(ll x, ll wc) {
    x = getfR(x,wc);
    auto A0 = lower_bound(cd[x].begin(),cd[x].end(),(pii){wc+1,-1});
    A0--;
    return (*A0).second;
}


ll fz(ll a, ll b, ll wc) {
    //cout << "fuse a,b,wc="<<a<<","<<b<<","<<wc<<"\n";
    deg[a]++;
    deg[b]++;
    bool SET = (deg[a]>=3)||(deg[b]>=3);
    a = getf(a,wc);
    b = getf(b,wc);
    //cout << "new a, new b="<<a<<","<<b<<"\n";
    if (a==b) {
        if (cd[a].back().first==wc) {
            cd[a].pop_back();
        }
        cd[a].push_back({wc,1});
        return a;
    }
    if (sz[a].back().second>sz[b].back().second) {
        swap(a,b);
    }
    if (f[a].back().first==wc){
        f[a].pop_back();
    }
    f[a].push_back({wc,b});
    if (sz[b].back().first==wc) {
        sz[b].pop_back();
    }
    sz[b].push_back({wc,sz[a].back().second+sz[b].back().second});
    if (cd[b].back().first==wc) {
        cd[b].pop_back();
    }
    cd[b].push_back({wc,(ll)((cd[b].back().second==1)||(cd[a].back().second==1))});
    if (SET) {
        if (cd[b].back().first==wc) {
            cd[b].pop_back();
        }
        cd[b].push_back({wc,1});
    }
    return b;
}


void init(int N, int M, vector<int> U, vector<int> V, vector<int> W1) {
    N1 = N; M1=M;
    vector<array<ll,3>> vedg;
    for (ll i=0;i<Nm;i++) {
        f[i].push_back({0,i});
        sz[i].push_back({0,1});
        cd[i].push_back({0,0});
        deg[i]=0;
    }
    for (ll i=0;i<M;i++) {
        vedg.push_back({W1[i],U[i],V[i]});
    }
    W = W1;
    sort(W.begin(),W.end());
    sort(vedg.begin(),vedg.end());
    for (auto A0: vedg) {
        fz(A0[1],A0[2],A0[0]);
    }
    for (ll i=0;i<Nm;i++) {
        for (ll x=0;x<(f[i].size()-1);x++) {
            assert(f[i][x].first<f[i][x+1].first);
        }
        for (ll x=0;x<(sz[i].size()-1);x++) {
            assert(sz[i][x].first<sz[i][x+1].first);
        }
        for (ll x=0;x<(cd[i].size()-1);x++) {
            assert(cd[i][x].first<cd[i][x+1].first);
        }
    }
}


int getMinimumFuelCapacity(int a, int b) {
    if (N1<=3 || M1==0) {
        return -1;
    }
    ll xmin = 0; ll xmax = W.size();
    while (xmin!=xmax) {
        ll xt = (xmin+xmax)/2;
        ll wt = W[xt];
        ll a1 = getfR(a,wt);
        ll b1 = getfR(b,wt);
        if (a1==b1 && getCD(a1,wt)==1) {
            xmax = xt;
        } else {
            xmin = xt+1;
        }
    }
    if (xmin==W.size()) {
        return -1;
    }
    return W[xmin];
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27