Submission #67374

#	Time	Username	Problem	Language	Result	Execution time	Memory
67374		top34051	Collapse (JOI18_collapse)	C++17	0 / 100	108 ms	39428 KiB

collapse

//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()) {
            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];
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));
    }
    vector<int> kuy;
    if(n>10000) return kuy;
//    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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35