oj.uz

Submission #603383

# Submission time Handle Problem Language Result Execution time Memory
603383 2022-07-24T05:51:16 Z 박상훈(#8426) Collapse (JOI18_collapse) C++17
0 / 100
 80 ms 28576 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();
        int m = (l+r)>>1;
        if (l==r) return;
        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();

    dsu.init(n);
    tree.init(1, 0, m-1);
    for (int i=0;i<m;i++) I[i].clear();
    for (int i=0;i<=n;i++) mp[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[X[i]][Y[i]] = -1;
        }
    }

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

}

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

    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17236 KB Output is correct
2 Incorrect 11 ms 16852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20112 KB Output is correct
2 Correct 32 ms 20148 KB Output is correct
3 Correct 80 ms 28576 KB Output is correct
4 Incorrect 35 ms 20308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17236 KB Output is correct
2 Incorrect 11 ms 16852 KB Output isn't correct
3 Halted 0 ms 0 KB -