oj.uz

Submission #603380

# Submission time Handle Problem Language Result Execution time Memory
603380 2022-07-24T05:48:55 Z 반딧불(#8427) Collapse (JOI18_collapse) C++17
0 / 100
 31 ms 3272 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);
}

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 4 ms 852 KB Output is correct
2 Incorrect 2 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3244 KB Output is correct
2 Incorrect 30 ms 3272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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