oj.uz

답안 #603372

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603372 2022-07-24T05:39:49 Z 박상훈(#8426) Collapse (JOI18_collapse) C++17
30 / 100
 170 ms 36480 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;
            //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;

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=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=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:72:20: warning: unused structured binding declaration [-Wunused-variable]
   72 |         for (auto &[x, y]:tree[i]) dsu.rollback();
      |                    ^~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17108 KB Output is correct
2 Incorrect 10 ms 16852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 19592 KB Output is correct
2 Correct 33 ms 19740 KB Output is correct
3 Correct 79 ms 26908 KB Output is correct
4 Correct 29 ms 20308 KB Output is correct
5 Correct 92 ms 29700 KB Output is correct
6 Correct 37 ms 21388 KB Output is correct
7 Correct 125 ms 35408 KB Output is correct
8 Correct 114 ms 31496 KB Output is correct
9 Correct 43 ms 21116 KB Output is correct
10 Correct 32 ms 21124 KB Output is correct
11 Correct 34 ms 21652 KB Output is correct
12 Correct 106 ms 33276 KB Output is correct
13 Correct 127 ms 35376 KB Output is correct
14 Correct 170 ms 36480 KB Output is correct
15 Correct 127 ms 36152 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 19660 KB Output is correct
2 Incorrect 29 ms 19616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17108 KB Output is correct
2 Incorrect 10 ms 16852 KB Output isn't correct
3 Halted 0 ms 0 KB -