oj.uz

Submission #603382

# Submission time Handle Problem Language Result Execution time Memory
603382 2022-07-24T05:50:20 Z 반딧불(#8427) Collapse (JOI18_collapse) C++17
30 / 100
 166 ms 17428 KB 
#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct unionFind{
    int par[100002];
    int cnt;
    vector<vector<pair<int*, int> > > history;

    void init(int _n){
        cnt = _n;
        for(int i=1; i<=_n; i++) par[i] = i;
    }

    void save(){
        history.push_back(vector<pair<int*, int> >());
    }

    void rollback(){
        for(int i=(int)history.back().size()-1; i>=0; i--){
            *(history.back()[i].first) = history.back()[i].second;
        }
        history.pop_back();
    }

    int find(int x){
        if(x==par[x]) return x;
        history.back().push_back(make_pair(&par[x], par[x]));
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        if(x==y) return;
        history.back().push_back(make_pair(&par[x], par[x]));
        par[x] = y;
        history.back().push_back(make_pair(&cnt, cnt));
        cnt--;
    }
} dsu;

struct Edge{
    int x, y, s, e;
    Edge(){}
    Edge(int x, int y, int s, int e): x(x), y(y), s(s), e(e){}
};

int n, m, q;
int ex[100002], ey[100002], et[100002];
int qx[100002], qt[100002];
int ans[100002];

void dnc(int s, int e, vector<Edge> &vec){
    if(s>e) return;
    dsu.save();
    vector<Edge> vl, vr, vnow;
    int mid = (s+e)/2;
    for(Edge edge: vec){
        if(edge.s <= s && e <= edge.e) vnow.push_back(edge);
        else{
            if(edge.s <= mid) vl.push_back(edge);
            if(mid < edge.e) vr.push_back(edge);
        }
    }
    for(Edge edge: vnow) dsu.merge(edge.x, edge.y);
    if(s==e){
        ans[s] = dsu.cnt;
        dsu.rollback();
        return;
    }
    dnc(s, mid, vl);
    dnc(mid+1, e, vr);
    dsu.rollback();
}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){
    n = N, m = (int)T.size(), q = (int)W.size();
    for(int i=1; i<=m; i++){
        ex[i] = X[i-1];
        ey[i] = Y[i-1];
        et[i] = T[i-1];
        ex[i]++, ey[i]++;
        if(ex[i] > ey[i]) swap(ex[i], ey[i]);
    }
    for(int i=1; i<=q; i++){
        qx[i] = P[i-1]+1;
        qt[i] = W[i-1]+1;
    }

    map<pair<int, int>, int> mp;
    vector<Edge> vec;
    for(int i=1; i<=m; i++){
        if(ex[i] <= qx[1] && qx[1] < ey[i]) continue;
        if(et[i] == 0) mp[make_pair(ex[i], ey[i])] = i;
        else{
            vec.push_back(Edge(ex[i], ey[i], mp[make_pair(ex[i], ey[i])], i-1));
            mp.erase(make_pair(ex[i], ey[i]));
        }
    }
    for(auto p: mp){
        pair<int, int> e = p.first;
        vec.push_back(Edge(e.first, e.second, p.second, m));
    }

    dsu.init(n);
    dnc(1, m, vec);
    vector<int> ret;
    for(int i=1; i<=q; i++) ret.push_back(ans[qt[i]]);
    return ret;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Incorrect 2 ms 468 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 3276 KB Output is correct
2 Correct 25 ms 3268 KB Output is correct
3 Correct 70 ms 8136 KB Output is correct
4 Correct 21 ms 3280 KB Output is correct
5 Correct 111 ms 8284 KB Output is correct
6 Correct 33 ms 3920 KB Output is correct
7 Correct 166 ms 16396 KB Output is correct
8 Correct 84 ms 8388 KB Output is correct
9 Correct 23 ms 3660 KB Output is correct
10 Correct 23 ms 3664 KB Output is correct
11 Correct 36 ms 3836 KB Output is correct
12 Correct 92 ms 8516 KB Output is correct
13 Correct 132 ms 12516 KB Output is correct
14 Correct 138 ms 16928 KB Output is correct
15 Correct 122 ms 17428 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3280 KB Output is correct
2 Incorrect 22 ms 3280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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