oj.uz

Submission #603366

# Submission time Handle Problem Language Result Execution time Memory
603366 2022-07-24T05:30:01 Z 박상훈(#8426) Collapse (JOI18_collapse) C++17
0 / 100
 35 ms 19728 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 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;
        }
        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;

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, m = T.size(), q = W.size();
    ans.resize(q);
    dsu.init(n);

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

        if (X[i] > Y[i]) swap(X[i], Y[i]);
        if (X[i] <= P[0] && P[0]+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=1;i<=n;i++){
        for (auto &[y, t]:mp[i]) if (t!=-1) tree.update(1, 0, m-1, t, m-1, i, y);
    }

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

    return ans;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17040 KB Output is correct
2 Incorrect 10 ms 16928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 19592 KB Output is correct
2 Incorrect 32 ms 19728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17040 KB Output is correct
2 Incorrect 10 ms 16928 KB Output isn't correct
3 Halted 0 ms 0 KB -