Submission #220728

#	Time	Username	Problem	Language	Result	Execution time	Memory
220728		balbit	Collapse (JOI18_collapse)	C++14	100 / 100	11869 ms	28400 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 998244353 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b) % mo;
}

const int maxn = 1e5+5;
const int BS = 150;

int state[maxn];
int ndel = 0; // Number of things that are connected
int ans[maxn], sz[maxn];
int par[maxn];
vector<int> stk;
int find(int x){
    return x == par[x]?x:find(par[x]);
}
void setup(){
    ndel = 0;
    stk.clear();
    for (int i = 0; i<maxn; ++i) par[i] = i, sz[i] = 1;
}
inline void undo(){
    if (!stk.empty()) {
        --ndel;
        sz[par[stk.back()]] -= sz[stk.back()];
        par[stk.back()] = stk.back();
        stk.pop_back();
    }
}
inline bool merge(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return 0;
    ++ndel;
    if (sz[a] < sz[b]) {
        swap(a,b);
    }
    stk.pb(b);
    sz[a] += sz[b];
    par[b] = a;
    return 1;
}

vector<pii > g[maxn]; // to, time
vector<pii> quat[maxn]; // For this position, what time do I query and what id is it?
int itof[maxn];
int ID[maxn];
bool notsure[maxn];
void go(int n,vector<int> TP,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) {
    // TP: query type, 0 is add, 1 is delete
    // X,Y: Edge endpoints
    // W: Query time
    // P: Query position
    // n: Length of the country
     memset(itof, 0, sizeof itof);
    int m = SZ(X), q = SZ(W);


    // SQRT by Time
    for (int t = 0; t<m; t += BS) {
        int t2 = min(m, t+BS);
        for (int i = t; i<t2; ++i) {
            notsure[ID[i]] = 1;
        }
        setup();
        for (int i = 0; i<n; ++i) {
            for (pii x : g[i]) {
                if (!notsure[x.s] && state[x.s]) {
                    merge(x.f,i);
                }
            }
            while (itof[i] < SZ(quat[i]) && quat[i][itof[i]] .f < t2) {
                int T = quat[i][itof[i]] .f, ansit = quat[i][itof[i]].s;
                assert(T >= t && T < t2);
                int nund = 0; // number of necessary undoes
                for (int j = t; j<=T; ++j) {
                    state[ID[j]]^=1;
                }
                for (int j = t; j<t2; ++j) {
                    if (Y[j] <=i && state[ID[j]]) {
                        nund += merge(X[j], Y[j]);
                    }
                }
                for (int j = t; j<=T; ++j) {
                    state[ID[j]]^=1;
                }
                ans[ansit] += ndel;
                ++itof[i];
                for (int cnt = 0; cnt < nund; ++cnt) undo();
            }
        }
        for (int i = t; i<t2; ++i) {
            state[ID[i]]^=1;
            notsure[ID[i]] = 0;
        }
    }

}

vector<int> simulateCollapse(int n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P){
    int q = SZ(P);
    vector<pii> all;
    for (int i = 0; i<SZ(X); ++i) {
        if (X[i] > Y[i]) swap(X[i], Y[i]);
        all.pb({X[i], Y[i]});
    }
    SORT_UNIQUE(all);
    for (int i = 0; i<SZ(X); ++i) {
        ID[i] = lower_bound(ALL(all), make_pair(X[i], Y[i])) - all.begin();
    }
    {
        set<pii> tmp;
        for (int i = 0; i<SZ(X); ++i) {
            if (X[i] > Y[i]) swap(X[i], Y[i]);
            if (!tmp.count({X[i], Y[i]})) {
                g[Y[i]].pb({X[i], ID[i]});
                tmp.insert({X[i], Y[i]});
            }
        }
        for (int i = 0; i<SZ(P); ++i) {
            quat[P[i]] .pb ({W[i], i});
        }
        for (int i = 0; i<n; ++i) {
            sort(ALL(quat[i]));
        }
        go(n,T,X,Y,W,P);
    }

    for (int i = 0; i<q; ++i) bug(i,ans[i]);

    for(int i = 0; i<n; ++i) g[i].clear(), quat[i].clear();
    memset(state, 0, sizeof state);
    for (int i = 0; i<SZ(X); ++i) {
        X[i] = n-X[i] - 1;
        Y[i] = n-Y[i] - 1;
    }
    for (int i = 0; i<SZ(P); ++i) {
        P[i] = n-P[i] - 2;
    }

    {
        set<pii> tmp;
        for (int i = 0; i<SZ(X); ++i) {
            if (X[i] > Y[i]) swap(X[i], Y[i]);
            if (!tmp.count({X[i], Y[i]})) {
                g[Y[i]].pb({X[i],ID[i]});
                tmp.insert({X[i], Y[i]});
            }
        }
        for (int i = 0; i<SZ(P); ++i) {
            quat[P[i]] .pb ({W[i], i});
        }
        for (int i = 0; i<n; ++i) {
            sort(ALL(quat[i]));
        }
        go(n,T,X,Y,W,P);
    }

    vector<int> re(q);

    for (int i = 0; i<q; ++i) {
        bug(i, ans[i]);
        re[i] = n-ans[i];
    }

	return re;

}
#ifdef BALBITe
signed main(){
    IOS();
    simulateCollapse(5,)


}
#endif

/*
4 4 9
0 0 2
0 1 3
0 2 3
1 2 3
1 0
1 1
1 2
2 0
2 1
2 2
3 0
3 1
3 2
*/

Compilation message (stderr)

collapse.cpp: In function 'void go(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:99:20: warning: unused variable 'q' [-Wunused-variable]
     int m = SZ(X), q = SZ(W);
                    ^

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35