oj.uz

Submission #220731

# Submission time Handle Problem Language Result Execution time Memory
220731 2020-04-08T13:40:04 Z balbit Collapse (JOI18_collapse) C++14
100 / 100
 6264 ms 25748 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 = 300;

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 11 ms 6784 KB Output is correct
3 Correct 13 ms 6784 KB Output is correct
4 Correct 13 ms 6784 KB Output is correct
5 Correct 35 ms 7040 KB Output is correct
6 Correct 37 ms 7296 KB Output is correct
7 Correct 10 ms 6912 KB Output is correct
8 Correct 11 ms 6912 KB Output is correct
9 Correct 37 ms 7424 KB Output is correct
10 Correct 46 ms 7416 KB Output is correct
11 Correct 53 ms 7544 KB Output is correct
12 Correct 48 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 10988 KB Output is correct
3 Correct 461 ms 14800 KB Output is correct
4 Correct 108 ms 10860 KB Output is correct
5 Correct 493 ms 15856 KB Output is correct
6 Correct 339 ms 12012 KB Output is correct
7 Correct 755 ms 21984 KB Output is correct
8 Correct 701 ms 19180 KB Output is correct
9 Correct 55 ms 10860 KB Output is correct
10 Correct 88 ms 11488 KB Output is correct
11 Correct 417 ms 11504 KB Output is correct
12 Correct 1788 ms 19988 KB Output is correct
13 Correct 2809 ms 22028 KB Output is correct
14 Correct 5122 ms 23832 KB Output is correct
15 Correct 3922 ms 24424 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 10092 KB Output is correct
2 Correct 67 ms 10080 KB Output is correct
3 Correct 83 ms 10472 KB Output is correct
4 Correct 102 ms 10600 KB Output is correct
5 Correct 367 ms 10344 KB Output is correct
6 Correct 360 ms 11240 KB Output is correct
7 Correct 687 ms 18796 KB Output is correct
8 Correct 1513 ms 22640 KB Output is correct
9 Correct 67 ms 12520 KB Output is correct
10 Correct 571 ms 12644 KB Output is correct
11 Correct 4716 ms 25208 KB Output is correct
12 Correct 6046 ms 25196 KB Output is correct
13 Correct 4864 ms 25644 KB Output is correct
14 Correct 6128 ms 25068 KB Output is correct
15 Correct 4790 ms 25748 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 11 ms 6784 KB Output is correct
3 Correct 13 ms 6784 KB Output is correct
4 Correct 13 ms 6784 KB Output is correct
5 Correct 35 ms 7040 KB Output is correct
6 Correct 37 ms 7296 KB Output is correct
7 Correct 10 ms 6912 KB Output is correct
8 Correct 11 ms 6912 KB Output is correct
9 Correct 37 ms 7424 KB Output is correct
10 Correct 46 ms 7416 KB Output is correct
11 Correct 53 ms 7544 KB Output is correct
12 Correct 48 ms 7544 KB Output is correct
13 Correct 45 ms 10092 KB Output is correct
14 Correct 68 ms 10988 KB Output is correct
15 Correct 461 ms 14800 KB Output is correct
16 Correct 108 ms 10860 KB Output is correct
17 Correct 493 ms 15856 KB Output is correct
18 Correct 339 ms 12012 KB Output is correct
19 Correct 755 ms 21984 KB Output is correct
20 Correct 701 ms 19180 KB Output is correct
21 Correct 55 ms 10860 KB Output is correct
22 Correct 88 ms 11488 KB Output is correct
23 Correct 417 ms 11504 KB Output is correct
24 Correct 1788 ms 19988 KB Output is correct
25 Correct 2809 ms 22028 KB Output is correct
26 Correct 5122 ms 23832 KB Output is correct
27 Correct 3922 ms 24424 KB Output is correct
28 Correct 49 ms 10092 KB Output is correct
29 Correct 67 ms 10080 KB Output is correct
30 Correct 83 ms 10472 KB Output is correct
31 Correct 102 ms 10600 KB Output is correct
32 Correct 367 ms 10344 KB Output is correct
33 Correct 360 ms 11240 KB Output is correct
34 Correct 687 ms 18796 KB Output is correct
35 Correct 1513 ms 22640 KB Output is correct
36 Correct 67 ms 12520 KB Output is correct
37 Correct 571 ms 12644 KB Output is correct
38 Correct 4716 ms 25208 KB Output is correct
39 Correct 6046 ms 25196 KB Output is correct
40 Correct 4864 ms 25644 KB Output is correct
41 Correct 6128 ms 25068 KB Output is correct
42 Correct 4790 ms 25748 KB Output is correct
43 Correct 711 ms 18132 KB Output is correct
44 Correct 854 ms 21632 KB Output is correct
45 Correct 928 ms 19564 KB Output is correct
46 Correct 1495 ms 22636 KB Output is correct
47 Correct 70 ms 12648 KB Output is correct
48 Correct 93 ms 12372 KB Output is correct
49 Correct 530 ms 12648 KB Output is correct
50 Correct 796 ms 14056 KB Output is correct
51 Correct 2363 ms 21484 KB Output is correct
52 Correct 3159 ms 22212 KB Output is correct
53 Correct 2710 ms 21880 KB Output is correct
54 Correct 3855 ms 23276 KB Output is correct
55 Correct 3299 ms 23020 KB Output is correct
56 Correct 3938 ms 24104 KB Output is correct
57 Correct 4594 ms 24644 KB Output is correct
58 Correct 5813 ms 24352 KB Output is correct
59 Correct 5129 ms 25412 KB Output is correct
60 Correct 6264 ms 24956 KB Output is correct