oj.uz

Submission #553292

# Submission time Handle Problem Language Result Execution time Memory
553292 2022-04-25T11:03:42 Z RaresFelix Collapse (JOI18_collapse) C++17
35 / 100
 15000 ms 428084 KB 
#include "collapse.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
using Edge = tuple<int, int, int, int>; //from, to, begin, end
using vEd = vector<Edge>;
using vi = vector<int>;

struct DSU { /// with roll_back
    int n;
    vector<int> P, S;
    DSU(int n) : n(n) {
        P.resize(n), S.assign(n, 1);
        for(int i = 0; i < n; ++i) P[i] = i;
    }
    int repr(int u) {
        return u == P[u] ? u : repr(P[u]);
    }
    int nr_uni = 0;
    stack<int> RP, RS;
    void uni(int u, int v) {
        u = repr(u), v = repr(v);
        if(u == v) return;
        if(S[u] < S[v]) swap(u, v);
        ++nr_uni, RP.push(v); RS.push(S[v]);
        P[v] = u, S[u] += S[v];
    }
    void roll_back(int update_count) {
        while(nr_uni > update_count) {
            --nr_uni;
            P[RP.top()] = RP.top();
            S[RP.top()] = RS.top();
            RP.pop(), RS.pop();
        }
    }
};

struct Bucket {
    DSU Simu;
    int begin, end;
    Bucket(int n, int begin, int end) : Simu(n), begin(begin), end(end) {}
    vector<Edge> idk;
    void add_edge(Edge nou) {
        auto &[f, t, b, e] = nou;
        if(e < begin || end < b) return;
        if(b <= begin && end <= e) { //complet
            Simu.uni(f, t);
            return;
        }
        idk.push_back(nou);
    }
    int query(int timp) {
        int count0 = Simu.nr_uni;
        for(auto &it : idk) {
            auto &[f, t, b, e] = it;
            if(b <= timp && timp <= e) Simu.uni(f, t);
        }
        int re = Simu.nr_uni;
        Simu.roll_back(count0);
        return re;
    }
};

void solve(int n, int c, int q, vEd &edges, vi &W, vi &P, vi &R) {
    R.assign(q, 0);
    vector<vi> Queries(n + 2);
    for(int i = 0; i < q; ++i)
        Queries[P[i]].push_back(i);
    vector<vEd> Add(n + 1);
    for(auto &[f, t, b, e] : edges)
        Add[t].push_back({f, t, b, e});

    int bucketSize = int(sqrt(c + 1));
    vector<Bucket> Sol;
    for(int lp = 0; lp <= c + 1; lp += bucketSize)
        Sol.emplace_back(n, lp, lp + bucketSize - 1);

    for(int i = 0; i < n; ++i) {
        for(auto &it : Add[i])
            for(auto &seg : Sol) seg.add_edge(it);
        for(auto &qid : Queries[i]) {
            int w = W[qid];
            int re = 0;
            for(auto &seg : Sol) {
                if(seg.begin <= w && w <= seg.end) {
                    re = seg.query(w);
                    break;
                }
            }
            R[qid] = i + 1 - re;
        }
    }
}

vector<int> simulateCollapse(
        int n,
        vector<int> T,
        vector<int> X,
        vector<int> Y,
        vector<int> W,
        vector<int> P
) {
    vEd edges;
    int c = T.size(), q = W.size();
    map<pair<int, int>, int> enabled;
    for(int i = 0 ; i < c; ++i)
        if(X[i] > Y[i]) swap(X[i], Y[i]);
    for(int i = 0 ; i < c; ++i) {
        if(!T[i])
            enabled[{X[i], Y[i]}] = i;
        else {
            edges.push_back({X[i], Y[i], enabled[{X[i], Y[i]}], i - 1});
            enabled[{X[i], Y[i]}] = -1;
        }
    }
    for(auto [p, e] : enabled) if(e != -1) {
            auto [f, t] = p;
            edges.push_back({f, t, e, c + 1});
        }
    vector<int> R, R1, R2;
    solve(n, c, q, edges, W, P, R1);
    for(auto &it : P) it = n - 2 - it;
    for(auto &[a, b, c, d] : edges)
        a = n - 1 - a, b = n - 1 - b, a ^= b, b ^= a, a ^= b;
    solve(n, c, q, edges, W, P, R2);
    for(int i = 0; i < q; ++i) R.push_back(R1[i] + R2[i]);
    return R;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 848 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 14 ms 1512 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 9 ms 1028 KB Output is correct
9 Correct 17 ms 6356 KB Output is correct
10 Correct 21 ms 6340 KB Output is correct
11 Correct 38 ms 6664 KB Output is correct
12 Correct 28 ms 6628 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3564 KB Output is correct
2 Correct 31 ms 3524 KB Output is correct
3 Correct 174 ms 9140 KB Output is correct
4 Correct 38 ms 3516 KB Output is correct
5 Correct 335 ms 10380 KB Output is correct
6 Correct 72 ms 4340 KB Output is correct
7 Correct 492 ms 25320 KB Output is correct
8 Correct 493 ms 52096 KB Output is correct
9 Correct 35 ms 11960 KB Output is correct
10 Correct 42 ms 15184 KB Output is correct
11 Correct 126 ms 59492 KB Output is correct
12 Correct 1085 ms 418008 KB Output is correct
13 Correct 2558 ms 422096 KB Output is correct
14 Correct 7192 ms 427424 KB Output is correct
15 Correct 3565 ms 426344 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3524 KB Output is correct
2 Correct 32 ms 3596 KB Output is correct
3 Correct 31 ms 3468 KB Output is correct
4 Correct 34 ms 3552 KB Output is correct
5 Correct 58 ms 3524 KB Output is correct
6 Correct 76 ms 4548 KB Output is correct
7 Correct 437 ms 20924 KB Output is correct
8 Correct 1805 ms 71588 KB Output is correct
9 Correct 78 ms 14300 KB Output is correct
10 Correct 176 ms 60756 KB Output is correct
11 Correct 4128 ms 428084 KB Output is correct
12 Execution timed out 15056 ms 424112 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 848 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 14 ms 1512 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 9 ms 1028 KB Output is correct
9 Correct 17 ms 6356 KB Output is correct
10 Correct 21 ms 6340 KB Output is correct
11 Correct 38 ms 6664 KB Output is correct
12 Correct 28 ms 6628 KB Output is correct
13 Correct 28 ms 3564 KB Output is correct
14 Correct 31 ms 3524 KB Output is correct
15 Correct 174 ms 9140 KB Output is correct
16 Correct 38 ms 3516 KB Output is correct
17 Correct 335 ms 10380 KB Output is correct
18 Correct 72 ms 4340 KB Output is correct
19 Correct 492 ms 25320 KB Output is correct
20 Correct 493 ms 52096 KB Output is correct
21 Correct 35 ms 11960 KB Output is correct
22 Correct 42 ms 15184 KB Output is correct
23 Correct 126 ms 59492 KB Output is correct
24 Correct 1085 ms 418008 KB Output is correct
25 Correct 2558 ms 422096 KB Output is correct
26 Correct 7192 ms 427424 KB Output is correct
27 Correct 3565 ms 426344 KB Output is correct
28 Correct 29 ms 3524 KB Output is correct
29 Correct 32 ms 3596 KB Output is correct
30 Correct 31 ms 3468 KB Output is correct
31 Correct 34 ms 3552 KB Output is correct
32 Correct 58 ms 3524 KB Output is correct
33 Correct 76 ms 4548 KB Output is correct
34 Correct 437 ms 20924 KB Output is correct
35 Correct 1805 ms 71588 KB Output is correct
36 Correct 78 ms 14300 KB Output is correct
37 Correct 176 ms 60756 KB Output is correct
38 Correct 4128 ms 428084 KB Output is correct
39 Execution timed out 15056 ms 424112 KB Time limit exceeded
40 Halted 0 ms 0 KB -