제출 #1141147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141147		Noproblem29	Collapse (JOI18_collapse)	C++20	0 / 100	15090 ms	2372 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long

struct ki{
	int x;
	ki *l=0;
	ki *r=0;
	ki *p=0;
	bool rev=0;
	ki()=default;
	ki(int v){x=v;}
	void push(){
		if(rev){
			rev=0;
			swap(l,r);
			if(l)l->rev^=1;
			if(r)r->rev^=1;
		}
	}
	bool adam(){
		return p==0||(p->l!=this&&p->r!=this);
	}
};
struct LCT{
	vector<ki>a;
	LCT(int n){
		a.resize(n+1);
		for(int i=1;i<=n;i++){
			a[i].x=i;
		}
	}
	void rot(ki *x){// literaly swaped father and son
		auto p=x->p;
		auto gp=p->p;
		if(!p->adam()){
			if(gp->r==p){
				gp->r=x;
			}
			else{
				gp->l=x;
			}
		}
		p->push();
		x->push();
		if(p->l==x){
			p->l=x->r;
			x->r=p;
			if(p->l)p->l->p=p;
		}
		else{
			p->r=x->l;
			x->l=p;
			if(p->r)p->r->p=p;
		}
		p->p=x;
		x->p=gp;

	}
	void splay(ki *x){ // i am the grand ,literaly how i understand
		while(!x->adam()){
			auto p=x->p;
			auto gp=p->p;
			if(!p->adam())rot((gp->r==p)==(p->r==x)?p:x);
			rot(x);
		}
		x->push();
	}
	ki *access(int v){
		ki *last=0;
		ki *x=&a[v];
		for(ki *p=x;p;p=p->p){
			splay(p);
			p->r=last;
			last=p;
		}
		splay(x);
		return last;
	} 
	void make_root(int v){
		access(v);
		ki *x=&a[v];
		if(x->l)x->l->rev^=1,x->l=0;
	}
	void merge(int x,int y){
		make_root(y);
		ki *v=&a[y];
		v->p=&a[x];
	}
	void cut(int x,int y){
		make_root(x);
		access(y);
		if(a[y].l){
			a[y].l->p=0;
			a[y].l=0;
		}
	}
	bool same(int x,int y){
		access(x);
		access(y);
		return a[x].p;
	}
};
int n,q;
vector<int> simulateCollapse(int _n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) {
	n=_n;
	q=W.size();
	vector<int>ans(q,0);
	for(int i=0;i<q;i++){
		LCT lc(n);
		ans[i]=n;
		for(int j=0;j<W[i];j++){
			if(X[j]>Y[j])swap(X[j],Y[j]);
			if(X[j]<=P[i]&&P[i]+1<=Y[j]){
				continue;
			}
			if(T[j]==0){
				if(!lc.same(X[j]+1,Y[j]+1)){
					ans[i]--;
				}
				lc.merge(X[j]+1,Y[j]+1);
			}
			else{
				lc.cut(X[j]+1,Y[j]+1);
				if(!lc.same(X[j]+1,Y[j]+1)){
					ans[i]++;
				}
			}
		}
	}

	return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35