oj.uz

Submission #220724

# Submission time Handle Problem Language Result Execution time Memory
220724 2020-04-08T13:10:09 Z balbit Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 24996 KB 
#include "collapse.h"
#include <bits/stdc++.h>
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;

map<pii, bool> state;
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;
}
void undo(){
    if (!stk.empty()) {
        --ndel;
        sz[par[stk.back()]] -= sz[stk.back()];
        par[stk.back()] = stk.back();
        stk.pop_back();
    }
}
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<int > g[maxn]; // to, time
vector<pii> quat[maxn]; // For this position, what time do I query and what id is it?
int itof[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) {
        set<pii> rm;
        int t2 = min(m, t+BS);
        for (int i = t; i<t2; ++i) {
            rm.insert({X[i], Y[i]});
        }
        setup();
        for (int i = 0; i<n; ++i) {
            for (int x : g[i]) {
                if (!rm.count({x,i}) && state[{x,i}]) {
                    merge(x,i);
                    bug("Bad merge Wtf?");
                }
            }
            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[{X[j], Y[j]}]^=1;
                }
                for (pii ele : rm) {
                    if (ele.s <=i && state[ele]) {
                        nund += merge(ele.f, ele.s);
                    }
                }
                for (int j = t; j<=T; ++j) {
                    state[{X[j], Y[j]}]^=1;
                }
                ans[ansit] += ndel;
                ++itof[i];
                for (int cnt = 0; cnt < nund; ++cnt) undo();
            }
        }
        for (int i = t; i<t2; ++i) {
            state[{X[i], Y[i]}]^=1;
        }
    }

}

vector<int> simulateCollapse(int n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P){
    int q = SZ(P);
    {
        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]);
                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();
    state.clear();
    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]);
                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:97: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 25 ms 6528 KB Output is correct
2 Correct 11 ms 6400 KB Output is correct
3 Correct 19 ms 6400 KB Output is correct
4 Correct 22 ms 6400 KB Output is correct
5 Correct 83 ms 6648 KB Output is correct
6 Correct 449 ms 7292 KB Output is correct
7 Correct 11 ms 6528 KB Output is correct
8 Correct 13 ms 6528 KB Output is correct
9 Correct 249 ms 7032 KB Output is correct
10 Correct 360 ms 7288 KB Output is correct
11 Correct 432 ms 7416 KB Output is correct
12 Correct 451 ms 7488 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9708 KB Output is correct
2 Correct 80 ms 10860 KB Output is correct
3 Correct 1447 ms 13196 KB Output is correct
4 Correct 275 ms 10988 KB Output is correct
5 Correct 6470 ms 15268 KB Output is correct
6 Correct 6222 ms 12056 KB Output is correct
7 Execution timed out 15082 ms 24996 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9708 KB Output is correct
2 Correct 80 ms 9840 KB Output is correct
3 Correct 142 ms 10104 KB Output is correct
4 Correct 286 ms 10132 KB Output is correct
5 Correct 3138 ms 10232 KB Output is correct
6 Correct 7217 ms 11260 KB Output is correct
7 Execution timed out 15011 ms 21480 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6528 KB Output is correct
2 Correct 11 ms 6400 KB Output is correct
3 Correct 19 ms 6400 KB Output is correct
4 Correct 22 ms 6400 KB Output is correct
5 Correct 83 ms 6648 KB Output is correct
6 Correct 449 ms 7292 KB Output is correct
7 Correct 11 ms 6528 KB Output is correct
8 Correct 13 ms 6528 KB Output is correct
9 Correct 249 ms 7032 KB Output is correct
10 Correct 360 ms 7288 KB Output is correct
11 Correct 432 ms 7416 KB Output is correct
12 Correct 451 ms 7488 KB Output is correct
13 Correct 44 ms 9708 KB Output is correct
14 Correct 80 ms 10860 KB Output is correct
15 Correct 1447 ms 13196 KB Output is correct
16 Correct 275 ms 10988 KB Output is correct
17 Correct 6470 ms 15268 KB Output is correct
18 Correct 6222 ms 12056 KB Output is correct
19 Execution timed out 15082 ms 24996 KB Time limit exceeded
20 Halted 0 ms 0 KB -