oj.uz

Submission #603388

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

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

# Verdict Execution time Memory Grader output
1 Correct 624 ms 17268 KB Output is correct
2 Incorrect 19 ms 16900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20048 KB Output is correct
2 Correct 33 ms 20112 KB Output is correct
3 Correct 90 ms 28552 KB Output is correct
4 Correct 32 ms 20244 KB Output is correct
5 Correct 106 ms 29588 KB Output is correct
6 Correct 37 ms 20900 KB Output is correct
7 Correct 130 ms 35188 KB Output is correct
8 Correct 123 ms 30920 KB Output is correct
9 Correct 36 ms 20876 KB Output is correct
10 Correct 33 ms 20892 KB Output is correct
11 Correct 38 ms 21148 KB Output is correct
12 Correct 133 ms 32388 KB Output is correct
13 Correct 131 ms 34656 KB Output is correct
14 Correct 130 ms 35736 KB Output is correct
15 Correct 128 ms 35472 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 20040 KB Output is correct
2 Incorrect 43 ms 20052 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 624 ms 17268 KB Output is correct
2 Incorrect 19 ms 16900 KB Output isn't correct
3 Halted 0 ms 0 KB -