oj.uz

Submission #67361

# Submission time Handle Problem Language Result Execution time Memory
67361 2018-08-14T06:54:49 Z top34051 Collapse (JOI18_collapse) C++17
0 / 100
 165 ms 39692 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 = 2e5 + 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--;
//        printf("\tadd_edge : %d -> %d (%d, %d)\n",x,y,u,v);
    }
    void pop_edge() {
        if(stk.empty()) return ;
        int x = stk.top().X, y = stk.top().Y; stk.pop();
        head[x] = x;
        if(x!=y) com++;
//        printf("\tpop_edge : %d -> %d\n",x,y);
    }
    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) {
//        printf("edge %d [%d, %d] : %d %d\n",pos,l,r,val.X,val.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) {
//        printf("res %d = %d\n",l,dsu.getcom());
        for(auto t : ask[l]) res[t.Y] = dsu.getcom();
    }
    else {
        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();
//    printf("end %d, %d : pop %d\n",l,r,tmp);
}

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-1));
            pos.erase({u,v});
        }
    }
    for(auto t : pos) {
        itv.push_back(node(t.X.X,t.X.Y,t.Y,m-1));
    }
//    for(auto t : itv) printf("itv %d %d %d %d\n",t.l,t.r,t.u,t.v);
    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 15 ms 10104 KB Output is correct
2 Incorrect 14 ms 10104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 13488 KB Output is correct
2 Correct 42 ms 13560 KB Output is correct
3 Runtime error 165 ms 39692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 35.0

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