oj.uz

Submission #603391

# Submission time Handle Problem Language Result Execution time Memory
603391 2022-07-24T05:59:54 Z 박상훈(#8426) Collapse (JOI18_collapse) C++17
35 / 100
 7675 ms 35740 KB 
#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<int> I[100100], ans;
map<int, int> mp[100100];
int n, m, q;

struct DSU{
    int path[100100], h[100100], ans;
    vector<pair<pair<int, int>, int>> _log;
    void init(int n){_log.clear(); ans = n; for (int i=1;i<=n;i++) path[i] = i, h[i] = 0;}
    int find(int s){
        if (s==path[s]) return s;
        return find(path[s]);
    }
    void merge(int s, int v){
        s = find(s), v = find(v);
        if (s==v){
            _log.emplace_back(make_pair(-1, -1), 0);
            return;
        }
        if (h[s] > h[v]) swap(s, v);

        path[s] = v;
        if (h[s]==h[v]){
            _log.emplace_back(make_pair(s, v), 1);
            h[v]++;
        }
        else{
            _log.emplace_back(make_pair(s, v), 0);
        }
        ans--;
    }
    void rollback(){
        assert(!_log.empty());
        auto [p, val] = _log.back(); _log.pop_back();
        if (p.first==-1) return;
        path[p.first] = p.first;
        ans++;
        if (val==1) h[p.second]--;
    }
}dsu;

struct Seg{
    vector<pair<int, int>> tree[400400];
    void init(int i, int l, int r){
        tree[i].clear();
        if (l==r) return;
        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
    }
    void update(int i, int l, int r, int s, int e, int x, int y){
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            tree[i].emplace_back(x, y);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x, y);
        update(i<<1|1, m+1, r, s, e, x, y);
    }

    void dfs(int i, int l, int r){
        for (auto &[x, y]:tree[i]) dsu.merge(x, y);

        if (l==r){
            for (auto &idx:I[l]) ans[idx] = dsu.ans;
            //if (l==m-1) printf("%d %d\n", dsu.find(0)==dsu.find(1), dsu.find(2)==dsu.find(4));
        }
        else{
            int m = (l+r)>>1;
            dfs(i<<1, l, m); dfs(i<<1|1, m+1, r);
        }

        for (auto &[x, y]:tree[i]) dsu.rollback();
    }
}tree;

void solve(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P,
	int L, int R
) {
    n = N, m = T.size(), q = W.size();
    //ans.resize(q);
    dsu.init(n);
    tree.init(1, 0, m-1);
    for (int i=0;i<m;i++) I[i].clear();

    for (int i=0;i<m;i++){

        if (X[i] > Y[i]) swap(X[i], Y[i]);
        if (X[i] <= P[L] && P[L]+1 <= Y[i]) continue;

        if (T[i]==0){
            mp[X[i]][Y[i]] = i;
        }
        else{
            tree.update(1, 0, m-1, mp[X[i]][Y[i]], i-1, X[i], Y[i]);
            mp[X[i]][Y[i]] = -1;
        }
    }

    for (int i=0;i<=n;i++){
        for (auto &[y, t]:mp[i]) if (t!=-1){
            tree.update(1, 0, m-1, t, m-1, i, y);
            mp[i][y] = -1;
        }
    }

    for (int i=L;i<=R;i++){
        I[W[i]].push_back(i);
    }
    tree.dfs(1, 0, m-1);

    //return ans;
}

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
) {
    ans.resize(W.size());
    if (N<=5000 && T.size()<=5000 && W.size()<=5000){
        for (int i=0;i<(int)W.size();i++) solve(N, T, X, Y, W, P, i, i);
    }
    else solve(N, T, X, Y, W, P, 0, (int)ans.size()-1);
    return ans;

}

Compilation message

collapse.cpp: In member function 'void Seg::dfs(int, int, int)':
collapse.cpp:78:20: warning: unused structured binding declaration [-Wunused-variable]
   78 |         for (auto &[x, y]:tree[i]) dsu.rollback();
      |                    ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 17100 KB Output is correct
2 Correct 18 ms 16852 KB Output is correct
3 Correct 32 ms 16888 KB Output is correct
4 Correct 37 ms 16852 KB Output is correct
5 Correct 3512 ms 17416 KB Output is correct
6 Correct 5964 ms 18144 KB Output is correct
7 Correct 49 ms 16928 KB Output is correct
8 Correct 56 ms 16924 KB Output is correct
9 Correct 3713 ms 17632 KB Output is correct
10 Correct 6438 ms 17808 KB Output is correct
11 Correct 7373 ms 17920 KB Output is correct
12 Correct 7675 ms 17908 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20056 KB Output is correct
2 Correct 32 ms 20116 KB Output is correct
3 Correct 86 ms 28568 KB Output is correct
4 Correct 37 ms 20244 KB Output is correct
5 Correct 115 ms 29516 KB Output is correct
6 Correct 38 ms 20912 KB Output is correct
7 Correct 122 ms 35136 KB Output is correct
8 Correct 105 ms 30876 KB Output is correct
9 Correct 40 ms 20884 KB Output is correct
10 Correct 37 ms 20752 KB Output is correct
11 Correct 38 ms 21076 KB Output is correct
12 Correct 108 ms 32412 KB Output is correct
13 Correct 131 ms 34636 KB Output is correct
14 Correct 139 ms 35740 KB Output is correct
15 Correct 173 ms 35380 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 20048 KB Output is correct
2 Incorrect 34 ms 20044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 17100 KB Output is correct
2 Correct 18 ms 16852 KB Output is correct
3 Correct 32 ms 16888 KB Output is correct
4 Correct 37 ms 16852 KB Output is correct
5 Correct 3512 ms 17416 KB Output is correct
6 Correct 5964 ms 18144 KB Output is correct
7 Correct 49 ms 16928 KB Output is correct
8 Correct 56 ms 16924 KB Output is correct
9 Correct 3713 ms 17632 KB Output is correct
10 Correct 6438 ms 17808 KB Output is correct
11 Correct 7373 ms 17920 KB Output is correct
12 Correct 7675 ms 17908 KB Output is correct
13 Correct 33 ms 20056 KB Output is correct
14 Correct 32 ms 20116 KB Output is correct
15 Correct 86 ms 28568 KB Output is correct
16 Correct 37 ms 20244 KB Output is correct
17 Correct 115 ms 29516 KB Output is correct
18 Correct 38 ms 20912 KB Output is correct
19 Correct 122 ms 35136 KB Output is correct
20 Correct 105 ms 30876 KB Output is correct
21 Correct 40 ms 20884 KB Output is correct
22 Correct 37 ms 20752 KB Output is correct
23 Correct 38 ms 21076 KB Output is correct
24 Correct 108 ms 32412 KB Output is correct
25 Correct 131 ms 34636 KB Output is correct
26 Correct 139 ms 35740 KB Output is correct
27 Correct 173 ms 35380 KB Output is correct
28 Correct 31 ms 20048 KB Output is correct
29 Incorrect 34 ms 20044 KB Output isn't correct
30 Halted 0 ms 0 KB -