oj.uz

Submission #220737

# Submission time Handle Problem Language Result Execution time Memory
220737 2020-04-08T13:53:06 Z balbit Collapse (JOI18_collapse) C++14
100 / 100
 4181 ms 25820 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 = 800;

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 41 ms 7040 KB Output is correct
2 Correct 11 ms 6784 KB Output is correct
3 Correct 12 ms 6784 KB Output is correct
4 Correct 15 ms 6912 KB Output is correct
5 Correct 69 ms 7032 KB Output is correct
6 Correct 63 ms 7292 KB Output is correct
7 Correct 11 ms 6912 KB Output is correct
8 Correct 12 ms 6912 KB Output is correct
9 Correct 59 ms 7416 KB Output is correct
10 Correct 89 ms 7416 KB Output is correct
11 Correct 92 ms 7544 KB Output is correct
12 Correct 86 ms 7504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 10100 KB Output is correct
2 Correct 78 ms 10860 KB Output is correct
3 Correct 1025 ms 14904 KB Output is correct
4 Correct 112 ms 10988 KB Output is correct
5 Correct 975 ms 15972 KB Output is correct
6 Correct 811 ms 12140 KB Output is correct
7 Correct 1180 ms 22084 KB Output is correct
8 Correct 1129 ms 19176 KB Output is correct
9 Correct 57 ms 10860 KB Output is correct
10 Correct 86 ms 11372 KB Output is correct
11 Correct 888 ms 11736 KB Output is correct
12 Correct 1604 ms 19940 KB Output is correct
13 Correct 2164 ms 21740 KB Output is correct
14 Correct 3312 ms 24080 KB Output is correct
15 Correct 2752 ms 24428 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 10096 KB Output is correct
2 Correct 68 ms 10208 KB Output is correct
3 Correct 88 ms 10600 KB Output is correct
4 Correct 103 ms 10600 KB Output is correct
5 Correct 648 ms 10344 KB Output is correct
6 Correct 845 ms 11284 KB Output is correct
7 Correct 1164 ms 18924 KB Output is correct
8 Correct 1713 ms 22636 KB Output is correct
9 Correct 68 ms 12520 KB Output is correct
10 Correct 1308 ms 12776 KB Output is correct
11 Correct 3300 ms 25300 KB Output is correct
12 Correct 4168 ms 25224 KB Output is correct
13 Correct 3402 ms 25708 KB Output is correct
14 Correct 4136 ms 25068 KB Output is correct
15 Correct 3343 ms 25820 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7040 KB Output is correct
2 Correct 11 ms 6784 KB Output is correct
3 Correct 12 ms 6784 KB Output is correct
4 Correct 15 ms 6912 KB Output is correct
5 Correct 69 ms 7032 KB Output is correct
6 Correct 63 ms 7292 KB Output is correct
7 Correct 11 ms 6912 KB Output is correct
8 Correct 12 ms 6912 KB Output is correct
9 Correct 59 ms 7416 KB Output is correct
10 Correct 89 ms 7416 KB Output is correct
11 Correct 92 ms 7544 KB Output is correct
12 Correct 86 ms 7504 KB Output is correct
13 Correct 46 ms 10100 KB Output is correct
14 Correct 78 ms 10860 KB Output is correct
15 Correct 1025 ms 14904 KB Output is correct
16 Correct 112 ms 10988 KB Output is correct
17 Correct 975 ms 15972 KB Output is correct
18 Correct 811 ms 12140 KB Output is correct
19 Correct 1180 ms 22084 KB Output is correct
20 Correct 1129 ms 19176 KB Output is correct
21 Correct 57 ms 10860 KB Output is correct
22 Correct 86 ms 11372 KB Output is correct
23 Correct 888 ms 11736 KB Output is correct
24 Correct 1604 ms 19940 KB Output is correct
25 Correct 2164 ms 21740 KB Output is correct
26 Correct 3312 ms 24080 KB Output is correct
27 Correct 2752 ms 24428 KB Output is correct
28 Correct 46 ms 10096 KB Output is correct
29 Correct 68 ms 10208 KB Output is correct
30 Correct 88 ms 10600 KB Output is correct
31 Correct 103 ms 10600 KB Output is correct
32 Correct 648 ms 10344 KB Output is correct
33 Correct 845 ms 11284 KB Output is correct
34 Correct 1164 ms 18924 KB Output is correct
35 Correct 1713 ms 22636 KB Output is correct
36 Correct 68 ms 12520 KB Output is correct
37 Correct 1308 ms 12776 KB Output is correct
38 Correct 3300 ms 25300 KB Output is correct
39 Correct 4168 ms 25224 KB Output is correct
40 Correct 3402 ms 25708 KB Output is correct
41 Correct 4136 ms 25068 KB Output is correct
42 Correct 3343 ms 25820 KB Output is correct
43 Correct 1222 ms 18236 KB Output is correct
44 Correct 1300 ms 21612 KB Output is correct
45 Correct 1499 ms 19308 KB Output is correct
46 Correct 1752 ms 22676 KB Output is correct
47 Correct 67 ms 12520 KB Output is correct
48 Correct 89 ms 12264 KB Output is correct
49 Correct 1103 ms 12520 KB Output is correct
50 Correct 1612 ms 13928 KB Output is correct
51 Correct 2146 ms 21696 KB Output is correct
52 Correct 2808 ms 22380 KB Output is correct
53 Correct 2485 ms 21872 KB Output is correct
54 Correct 3201 ms 23148 KB Output is correct
55 Correct 2831 ms 23024 KB Output is correct
56 Correct 2991 ms 23916 KB Output is correct
57 Correct 3227 ms 24684 KB Output is correct
58 Correct 3889 ms 24424 KB Output is correct
59 Correct 3325 ms 25580 KB Output is correct
60 Correct 4181 ms 25224 KB Output is correct