oj.uz

Submission #1012954

# Submission time Handle Problem Language Result Execution time Memory
1012954 2024-07-03T02:07:13 Z Cookie Collapse (JOI18_collapse) C++14
100 / 100
 4633 ms 235040 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,tune=native")
//huhu
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#define ull unsigned long long
const int mxn = 1e5 + 5, inf = 1e9 + 5, sq = 350;
 
#include "collapse.h"
int n;
struct DSU{
    int pa[mxn + 1];
    vt<int>comp;
    void init(){
        for(int i = 0; i < n; i++)pa[i] = -1;
    }
    int fp(int u){
        if(pa[u] < 0)return(u);
        return(pa[u] = fp(pa[u]));
    }
    bool unon(int u, int v){
        comp.pb(u); comp.pb(v);
        u = fp(u); v = fp(v);
        if(u == v)return(0);
        if(-pa[u] < -pa[v])swap(u, v);
        pa[u] += pa[v]; pa[v] = u;
        return(1);
    }
    void reset(){
        for(auto i: comp){
            pa[i] = -1;
        }
        comp.clear();
    }
};
struct Q{
    int tme, p, id;
    bool operator <(const Q &other){
        return(p < other.p);
    }
};
vt<Q>queries;
bool cmpl(pii a, pii b){
    return(a.se < b.se);
}
bool cmpr(pii a, pii b){
    return(a.fi > b.fi);
}
vt<int>t, x, y, w, p, res;
set<pair<int, int>>all; // edges after block[i - 1]
vt<pii>inblock[mxn + 1]; // edges that appear in block
void solve(int l, int r){
    set<pair<int, int>>remain = all;
    for(int i = l; i <= r; i++){
        if(t[i] == 1 && remain.count(mpp(x[i], y[i]))){
            remain.erase(mpp(x[i], y[i]));
        }
    }
    
    map<pair<int, int>, int>last;
    for(int i = l; i <= r; i++){
        if(t[i] == 0){
            assert(last.find(mpp(x[i], y[i])) == last.end());
            last[mpp(x[i], y[i])] = i;
        }else{
            int lt = ((last.find(mpp(x[i], y[i])) == last.end()) ? l : last[mpp(x[i], y[i])]);
            for(int j = lt; j < i; j++){
                inblock[j].pb(mpp(x[i], y[i]));
            }
            last.erase(mpp(x[i], y[i]));
        }
    }
    
    for(auto i: last){
        for(int j = i.se; j <= r; j++){
            inblock[j].pb(i.fi);
        }
    }
    vt<pii>edge;
    for(auto i: remain)edge.pb(i);
    sort(ALL(edge), cmpl);
    vt<Q>curr;
    for(auto i: queries){
        if(i.tme >= l && i.tme <= r){
            curr.pb({i.tme, i.p, i.id});
        }
    }
    sort(ALL(curr));
    int lp = 0;
    DSU dsu, dsu2; dsu.init();  dsu2.init();
    int cnt = 0; //global connection 
    for(auto [tme, pl, id]: curr){
        while(lp < sz(edge) && edge[lp].se <= pl){
            cnt += dsu.unon(edge[lp].fi, edge[lp].se); lp++;
        }
        int cnt2 = cnt; // connection for this query only 
        for(auto [u, v]: inblock[tme]){
            if(v <= pl){
                cnt2 += dsu2.unon(dsu.fp(u), dsu.fp(v));
            }
        }
        dsu2.reset();
        res[id] += (pl) - cnt2;
    }
    dsu.init(); dsu2.init();
    curr.clear();
    // same thing but for right side :>
    for(auto i: queries){
        if(i.tme >= l && i.tme <= r){
            curr.pb({i.tme, i.p + 1, i.id});
        }
    }
    sort(ALLR(curr));
    sort(ALL(edge), cmpr);
    int rp = 0;
    cnt = 0; //global connection 
    for(auto [tme, pr, id]: curr){
        while(rp < sz(edge) && edge[rp].fi >= pr){
            cnt += dsu.unon(edge[rp].fi, edge[rp].se); rp++;
        }
        int cnt2 = cnt; // connection for this query only 
        for(auto [u, v]: inblock[tme]){
            if(u >= pr){
                cnt2 += dsu2.unon(dsu.fp(u), dsu.fp(v));
            }
        }
        dsu2.reset();
        res[id] += (n - pr + 1) - cnt2;
    }
    for(int i = l; i <= r; i++){
        if(t[i] == 0)all.insert(mpp(x[i], y[i]));
        else all.erase(mpp(x[i], y[i]));
    }
    
}

std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
    n = N; t = T; x = X; y = Y; w = W; p = P;
    for(int i = 0; i < sz(x); i++){
        if(x[i] > y[i])swap(x[i], y[i]);
    }
    for(int i = 0; i < sz(w); i++){
        queries.pb({w[i], p[i], i});
    }
    res.resize(sz(queries));
	int l = 0;
	for(int i = 0; i < sz(t); i += sq){
	    solve(i, min(i + sq - 1, sz(t) - 1));
	}
	return(res);
}
 
 /*
int main(int argc, char *argv[]) {
	int N, C, Q;
	scanf("%d%d%d", &N, &C, &Q);
	std::vector<int> T(C), X(C), Y(C);
	for(int i = 0; i < C; i++) {
		scanf("%d%d%d", &T[i], &X[i], &Y[i]);
	}
	std::vector<int> W(Q), P(Q);
	for(int i = 0; i < Q; i++) {
		scanf("%d%d", &W[i], &P[i]);
	}
	auto res = simulateCollapse(N, T, X, Y, W, P);
	for(auto i : res) {
		printf("%d\n", i);
	}
}
*/

Compilation message

collapse.cpp: In function 'void solve(int, int)':
collapse.cpp:108:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |     for(auto [tme, pl, id]: curr){
      |              ^
collapse.cpp:113:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |         for(auto [u, v]: inblock[tme]){
      |                  ^
collapse.cpp:133:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  133 |     for(auto [tme, pr, id]: curr){
      |              ^
collapse.cpp:138:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |         for(auto [u, v]: inblock[tme]){
      |                  ^
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:169:6: warning: unused variable 'l' [-Wunused-variable]
  169 |  int l = 0;
      |      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3932 KB Output is correct
2 Correct 3 ms 3932 KB Output is correct
3 Correct 3 ms 3932 KB Output is correct
4 Correct 4 ms 3932 KB Output is correct
5 Correct 6 ms 4700 KB Output is correct
6 Correct 26 ms 14916 KB Output is correct
7 Correct 3 ms 3932 KB Output is correct
8 Correct 3 ms 3932 KB Output is correct
9 Correct 7 ms 4956 KB Output is correct
10 Correct 20 ms 12124 KB Output is correct
11 Correct 27 ms 14940 KB Output is correct
12 Correct 26 ms 14948 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10188 KB Output is correct
2 Correct 29 ms 9960 KB Output is correct
3 Correct 227 ms 40388 KB Output is correct
4 Correct 34 ms 10196 KB Output is correct
5 Correct 343 ms 102088 KB Output is correct
6 Correct 131 ms 19396 KB Output is correct
7 Correct 3326 ms 231764 KB Output is correct
8 Correct 337 ms 114632 KB Output is correct
9 Correct 26 ms 10448 KB Output is correct
10 Correct 29 ms 10452 KB Output is correct
11 Correct 93 ms 11112 KB Output is correct
12 Correct 341 ms 103876 KB Output is correct
13 Correct 1571 ms 202680 KB Output is correct
14 Correct 3779 ms 232224 KB Output is correct
15 Correct 3062 ms 232176 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10192 KB Output is correct
2 Correct 28 ms 10188 KB Output is correct
3 Correct 31 ms 10192 KB Output is correct
4 Correct 47 ms 10192 KB Output is correct
5 Correct 115 ms 11216 KB Output is correct
6 Correct 141 ms 19468 KB Output is correct
7 Correct 1984 ms 179380 KB Output is correct
8 Correct 4056 ms 234664 KB Output is correct
9 Correct 37 ms 10448 KB Output is correct
10 Correct 130 ms 11332 KB Output is correct
11 Correct 3578 ms 234928 KB Output is correct
12 Correct 4202 ms 234908 KB Output is correct
13 Correct 3804 ms 234972 KB Output is correct
14 Correct 4356 ms 234884 KB Output is correct
15 Correct 4083 ms 234852 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3932 KB Output is correct
2 Correct 3 ms 3932 KB Output is correct
3 Correct 3 ms 3932 KB Output is correct
4 Correct 4 ms 3932 KB Output is correct
5 Correct 6 ms 4700 KB Output is correct
6 Correct 26 ms 14916 KB Output is correct
7 Correct 3 ms 3932 KB Output is correct
8 Correct 3 ms 3932 KB Output is correct
9 Correct 7 ms 4956 KB Output is correct
10 Correct 20 ms 12124 KB Output is correct
11 Correct 27 ms 14940 KB Output is correct
12 Correct 26 ms 14948 KB Output is correct
13 Correct 21 ms 10188 KB Output is correct
14 Correct 29 ms 9960 KB Output is correct
15 Correct 227 ms 40388 KB Output is correct
16 Correct 34 ms 10196 KB Output is correct
17 Correct 343 ms 102088 KB Output is correct
18 Correct 131 ms 19396 KB Output is correct
19 Correct 3326 ms 231764 KB Output is correct
20 Correct 337 ms 114632 KB Output is correct
21 Correct 26 ms 10448 KB Output is correct
22 Correct 29 ms 10452 KB Output is correct
23 Correct 93 ms 11112 KB Output is correct
24 Correct 341 ms 103876 KB Output is correct
25 Correct 1571 ms 202680 KB Output is correct
26 Correct 3779 ms 232224 KB Output is correct
27 Correct 3062 ms 232176 KB Output is correct
28 Correct 21 ms 10192 KB Output is correct
29 Correct 28 ms 10188 KB Output is correct
30 Correct 31 ms 10192 KB Output is correct
31 Correct 47 ms 10192 KB Output is correct
32 Correct 115 ms 11216 KB Output is correct
33 Correct 141 ms 19468 KB Output is correct
34 Correct 1984 ms 179380 KB Output is correct
35 Correct 4056 ms 234664 KB Output is correct
36 Correct 37 ms 10448 KB Output is correct
37 Correct 130 ms 11332 KB Output is correct
38 Correct 3578 ms 234928 KB Output is correct
39 Correct 4202 ms 234908 KB Output is correct
40 Correct 3804 ms 234972 KB Output is correct
41 Correct 4356 ms 234884 KB Output is correct
42 Correct 4083 ms 234852 KB Output is correct
43 Correct 299 ms 74692 KB Output is correct
44 Correct 3537 ms 234352 KB Output is correct
45 Correct 338 ms 105560 KB Output is correct
46 Correct 3890 ms 234532 KB Output is correct
47 Correct 35 ms 10448 KB Output is correct
48 Correct 37 ms 10472 KB Output is correct
49 Correct 113 ms 11044 KB Output is correct
50 Correct 224 ms 33744 KB Output is correct
51 Correct 448 ms 116816 KB Output is correct
52 Correct 1193 ms 215668 KB Output is correct
53 Correct 1106 ms 215392 KB Output is correct
54 Correct 1993 ms 203160 KB Output is correct
55 Correct 1739 ms 203608 KB Output is correct
56 Correct 2525 ms 216492 KB Output is correct
57 Correct 3387 ms 230980 KB Output is correct
58 Correct 3877 ms 230440 KB Output is correct
59 Correct 4037 ms 234956 KB Output is correct
60 Correct 4633 ms 235040 KB Output is correct