oj.uz

Submission #220730

# Submission time Handle Problem Language Result Execution time Memory
220730 2020-04-08T13:37:20 Z balbit Collapse (JOI18_collapse) C++14
100 / 100
 7112 ms 25900 KB 
#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 = 250;

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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7040 KB Output is correct
2 Correct 10 ms 6784 KB Output is correct
3 Correct 12 ms 6784 KB Output is correct
4 Correct 16 ms 6784 KB Output is correct
5 Correct 32 ms 7040 KB Output is correct
6 Correct 33 ms 7296 KB Output is correct
7 Correct 11 ms 6912 KB Output is correct
8 Correct 12 ms 6912 KB Output is correct
9 Correct 35 ms 7296 KB Output is correct
10 Correct 44 ms 7416 KB Output is correct
11 Correct 49 ms 7552 KB Output is correct
12 Correct 46 ms 7544 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 10092 KB Output is correct
2 Correct 68 ms 10860 KB Output is correct
3 Correct 405 ms 14828 KB Output is correct
4 Correct 109 ms 11116 KB Output is correct
5 Correct 462 ms 15852 KB Output is correct
6 Correct 298 ms 12140 KB Output is correct
7 Correct 768 ms 21996 KB Output is correct
8 Correct 685 ms 19304 KB Output is correct
9 Correct 53 ms 10860 KB Output is correct
10 Correct 82 ms 11488 KB Output is correct
11 Correct 365 ms 11508 KB Output is correct
12 Correct 1924 ms 20204 KB Output is correct
13 Correct 2842 ms 21996 KB Output is correct
14 Correct 5831 ms 23924 KB Output is correct
15 Correct 4605 ms 24428 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10100 KB Output is correct
2 Correct 66 ms 10204 KB Output is correct
3 Correct 84 ms 10600 KB Output is correct
4 Correct 108 ms 10600 KB Output is correct
5 Correct 339 ms 10216 KB Output is correct
6 Correct 320 ms 11476 KB Output is correct
7 Correct 653 ms 18796 KB Output is correct
8 Correct 1617 ms 22636 KB Output is correct
9 Correct 74 ms 12520 KB Output is correct
10 Correct 499 ms 12520 KB Output is correct
11 Correct 5450 ms 25652 KB Output is correct
12 Correct 7112 ms 25096 KB Output is correct
13 Correct 5639 ms 25552 KB Output is correct
14 Correct 6926 ms 25336 KB Output is correct
15 Correct 5577 ms 25900 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7040 KB Output is correct
2 Correct 10 ms 6784 KB Output is correct
3 Correct 12 ms 6784 KB Output is correct
4 Correct 16 ms 6784 KB Output is correct
5 Correct 32 ms 7040 KB Output is correct
6 Correct 33 ms 7296 KB Output is correct
7 Correct 11 ms 6912 KB Output is correct
8 Correct 12 ms 6912 KB Output is correct
9 Correct 35 ms 7296 KB Output is correct
10 Correct 44 ms 7416 KB Output is correct
11 Correct 49 ms 7552 KB Output is correct
12 Correct 46 ms 7544 KB Output is correct
13 Correct 45 ms 10092 KB Output is correct
14 Correct 68 ms 10860 KB Output is correct
15 Correct 405 ms 14828 KB Output is correct
16 Correct 109 ms 11116 KB Output is correct
17 Correct 462 ms 15852 KB Output is correct
18 Correct 298 ms 12140 KB Output is correct
19 Correct 768 ms 21996 KB Output is correct
20 Correct 685 ms 19304 KB Output is correct
21 Correct 53 ms 10860 KB Output is correct
22 Correct 82 ms 11488 KB Output is correct
23 Correct 365 ms 11508 KB Output is correct
24 Correct 1924 ms 20204 KB Output is correct
25 Correct 2842 ms 21996 KB Output is correct
26 Correct 5831 ms 23924 KB Output is correct
27 Correct 4605 ms 24428 KB Output is correct
28 Correct 47 ms 10100 KB Output is correct
29 Correct 66 ms 10204 KB Output is correct
30 Correct 84 ms 10600 KB Output is correct
31 Correct 108 ms 10600 KB Output is correct
32 Correct 339 ms 10216 KB Output is correct
33 Correct 320 ms 11476 KB Output is correct
34 Correct 653 ms 18796 KB Output is correct
35 Correct 1617 ms 22636 KB Output is correct
36 Correct 74 ms 12520 KB Output is correct
37 Correct 499 ms 12520 KB Output is correct
38 Correct 5450 ms 25652 KB Output is correct
39 Correct 7112 ms 25096 KB Output is correct
40 Correct 5639 ms 25552 KB Output is correct
41 Correct 6926 ms 25336 KB Output is correct
42 Correct 5577 ms 25900 KB Output is correct
43 Correct 669 ms 18132 KB Output is correct
44 Correct 842 ms 21484 KB Output is correct
45 Correct 929 ms 19436 KB Output is correct
46 Correct 1673 ms 22636 KB Output is correct
47 Correct 76 ms 12392 KB Output is correct
48 Correct 90 ms 12264 KB Output is correct
49 Correct 464 ms 12520 KB Output is correct
50 Correct 733 ms 14056 KB Output is correct
51 Correct 2597 ms 21484 KB Output is correct
52 Correct 3477 ms 22380 KB Output is correct
53 Correct 2955 ms 21996 KB Output is correct
54 Correct 4314 ms 23324 KB Output is correct
55 Correct 3624 ms 22972 KB Output is correct
56 Correct 4424 ms 23648 KB Output is correct
57 Correct 5068 ms 24556 KB Output is correct
58 Correct 6198 ms 24556 KB Output is correct
59 Correct 5503 ms 25836 KB Output is correct
60 Correct 6945 ms 25200 KB Output is correct