oj.uz

Submission #67355

# Submission time Handle Problem Language Result Execution time Memory
67355 2018-08-14T06:28:03 Z top34051 Collapse (JOI18_collapse) C++17
0 / 100
 41 ms 10576 KB 
//S2
#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;

class dsu_type{
public:
    int n, com;
    int head[maxn];
    stack<pii> stk;
    int findhead(int x) {
        if(x==head[x]) return x;
        return findhead(head[x]);
    }
    void init(int _n) {
        n = com = _n;
        for(int i=0;i<n;i++) head[i] = i;
    }
    void add_edge(int u, int v) {
        int x = findhead(u), y = findhead(v);
        stk.push({x,y});
        head[x] = y;
        if(x!=y) com--;
    }
    void pop_edge() {
        int x = stk.top().X, y = stk.top().Y;
        head[x] = x;
        if(x!=y) com++;
    }
    int getcom() {
        return com;
    }
} dsu;

struct node {
    int u,v,l,r;
    node(int _u = 0, int _v = 0, int _l = 0, int _r = 0) {
        u = _u; v = _v; l = _l; r = _r;
    }
};

int n,m,q;
map<pii,int> pos;
vector<node> itv;
vector<pii> ask[maxn];
vector<pii> edge[maxn];
int res[maxn];

void update(int pos, int l, int r, int x, int y, pii val) {
    if(l>r || r<x || y<l) return ;
    if(x<=l && r<=y) {
        edge[pos].push_back(val);
        return ;
    }
    int mid = (l+r)/2;
    update(pos<<1,l,mid,x,y,val);
    update(pos<<1|1,mid+1,r,x,y,val);
}

void solve(int pos, int l, int r) {
    for(auto t : edge[pos]) dsu.add_edge(t.X,t.Y);
    if(l==r) {
        for(auto t : ask[l]) res[t.Y] = dsu.getcom();
        return ;
    }
    int mid = (l+r)/2;
    solve(pos<<1,l,mid);
    solve(pos<<1|1,mid+1,r);
    int tmp = edge[pos].size();
    for(int i=0;i<tmp;i++) dsu.pop_edge();
}

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();
    for(int i=0;i<m;i++) {
        int u = X[i], v = Y[i];
        if(u>v) swap(u,v);
        if(u<=P[0] && P[0]+1<=v) continue;
        if(T[i]==0) pos[{u,v}] = i;
        else {
            itv.push_back(node(u,v,pos[{u,v}],i));
            pos.erase({u,v});
        }
    }
    for(auto t : pos) {
        itv.push_back(node(t.X.X,t.X.Y,t.Y,m-1));
    }
    for(int i=0;i<q;i++) {
        ask[W[i]].push_back({P[i],i});
    }

    dsu.init(n);
    for(auto t : itv) update(1,0,m-1,t.l,t.r,{t.u,t.v});
    solve(1,0,m-1);

    vector<int> vec;
    for(int i=0;i<q;i++) vec.push_back(res[i]);
    return vec;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9272 KB Output is correct
2 Incorrect 40 ms 9800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 10308 KB Output is correct
2 Incorrect 38 ms 10576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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