oj.uz

Submission #67386

# Submission time Handle Problem Language Result Execution time Memory
67386 2018-08-14T07:22:09 Z top34051 Collapse (JOI18_collapse) C++17
30 / 100
 4679 ms 50388 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--;
//        printf("\tadd_edge : %d -> %d (%d, %d)\n",x,y,u,v);
    }
    void pop_edge() {
        if(stk.empty()) {
            printf("hello");
            exit(0);
            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*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 22 ms 12536 KB Output is correct
2 Incorrect 13 ms 12536 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 43 ms 15756 KB Output is correct
2 Correct 61 ms 15828 KB Output is correct
3 Correct 140 ms 23252 KB Output is correct
4 Correct 42 ms 23252 KB Output is correct
5 Correct 141 ms 26452 KB Output is correct
6 Correct 56 ms 26452 KB Output is correct
7 Correct 889 ms 35476 KB Output is correct
8 Correct 191 ms 35476 KB Output is correct
9 Correct 53 ms 35476 KB Output is correct
10 Correct 56 ms 35476 KB Output is correct
11 Correct 57 ms 35476 KB Output is correct
12 Correct 210 ms 39760 KB Output is correct
13 Correct 3085 ms 44540 KB Output is correct
14 Correct 270 ms 48076 KB Output is correct
15 Correct 4679 ms 50388 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 35.0

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