oj.uz

Submission #67447

# Submission time Handle Problem Language Result Execution time Memory
67447 2018-08-14T09:52:44 Z top34051 Collapse (JOI18_collapse) C++17
30 / 100
 293 ms 31100 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], sz[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;
                sz[i] = 1;
            }
            while(!stk.empty()) stk.pop();
        }
        void add_edge(int u, int v) {
            int x = findhead(u), y = findhead(v);
            if(sz[x] > sz[y]) swap(x,y);
            stk.push({x,y});
            if(x!=y) {
                head[x] = y;
                sz[y] += sz[x];
                com--;
            }
        }
        void pop_edge() {
            int x = stk.top().X, y = stk.top().Y; stk.pop();
            if(x!=y) {
                head[x] = x;
                sz[y] -= sz[x];
                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*4];
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[{u,v}] = -1;
        }
    }
    for(auto t : pos) {
        if(t.Y==-1) continue;
        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 18 ms 12408 KB Output is correct
2 Incorrect 16 ms 12408 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 46 ms 15924 KB Output is correct
2 Correct 49 ms 15924 KB Output is correct
3 Correct 154 ms 23172 KB Output is correct
4 Correct 43 ms 23172 KB Output is correct
5 Correct 173 ms 24452 KB Output is correct
6 Correct 66 ms 24452 KB Output is correct
7 Correct 288 ms 30728 KB Output is correct
8 Correct 169 ms 30728 KB Output is correct
9 Correct 48 ms 30728 KB Output is correct
10 Correct 84 ms 30728 KB Output is correct
11 Correct 58 ms 30728 KB Output is correct
12 Correct 241 ms 30728 KB Output is correct
13 Correct 280 ms 30728 KB Output is correct
14 Correct 238 ms 31100 KB Output is correct
15 Correct 293 ms 31100 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 35.0

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