Submission #612747

#	Time	Username	Problem	Language	Result	Execution time	Memory
612747		nohaxjustsoflo	Game (IOI14_game)	C++17	15 / 100	6 ms	724 KiB

game

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=3003;
const int mod=998244353;
const int mxlogN=40;
const int mxK=26;
const ll inf=1e18;
const int K=600;


#define pii pair<int,int>
#define pb push_back
const int N=1501;
const int L=1501;
const int M=N*L*2;
stack<int> reu;
int tsz,go[M][2],fa[M],sz[M],my_mask[M],mask[M];
pii my_edg[M];
int New(){
	int x;if(reu.empty())x=++tsz;else x=reu.top(),reu.pop();
	go[x][0]=go[x][1]=fa[x]=0;sz[x]=1;my_mask[x]=mask[x]=0;
	return x;
}
void Free(int x){reu.push(x);go[x][0]=go[x][1]=fa[x]=sz[x]=my_mask[x]=mask[x]=0;my_edg[x]={0,0};}
void pull(int x){assert(x!=0);sz[x]=sz[go[x][0]]+1+sz[go[x][1]];mask[x]=mask[go[x][0]]|my_mask[x]|mask[go[x][1]];}
int pd(int x){return go[fa[x]][0]==x?0:go[fa[x]][1]==x?1:-1;}
void rot(int x){
	int y=fa[x],z=fa[y],p=pd(x),q=pd(y),w=go[x][p^1];
	if(~q)go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
	if(w)fa[w]=y;fa[y]=x;fa[x]=z;
	pull(y);pull(x);
}
void splay(int x){for(;~pd(x);rot(x))if(~pd(fa[x]))rot(pd(x)==pd(fa[x])?fa[x]:x);}
int exp_r(int x){splay(x);while(go[x][1])x=go[x][1];splay(x);return x;}
int exp_l(int x){splay(x);while(go[x][0])x=go[x][0];splay(x);return x;}
void mrg(int x,int y){if(x&&y)x=exp_r(x),splay(y),go[x][1]=y,fa[y]=x,pull(x);}
int Find(int x,int m){
	if(mask[go[x][0]]&m)return Find(go[x][0],m);
	if(my_mask[x]&m)return x;
	return Find(go[x][1],m);
}
void fir(int x){splay(x);if(go[x][0]){int y=go[x][0];fa[y]=0;go[x][0]=0;pull(x);mrg(x,y);}}
void cut(int x){
	splay(x);
	int y=go[x][0],z=go[x][1];
	fa[y]=fa[z]=0;Free(x);
}
struct EulerTourTree{
	set<pii> E,A;
	map<pii,int> edg;
	EulerTourTree(){}
	void init(){E.clear();A.clear();edg.clear();}
	bool empty_e(int x){auto it=E.lower_bound({x,0});return it==E.end()||it->first!=x;}
	bool empty_a(int x){auto it=A.lower_bound({x,0});return it==A.end()||it->first!=x;}
	int node(int x){
		auto it=edg.lower_bound({x,0});
		if(it==edg.end()||it->first.first!=x)return 0;
		return it->second;
	}
	void cng_rt(int x){x=node(x);if(!x)return;fir(x);}
	int find_rt(int x){if(!node(x))return x;return my_edg[exp_l(node(x))].first;}
	bool con(int x,int y){return find_rt(x)==find_rt(y);}
	void add_mask(int x){int nd=node(x);if(nd)splay(nd),my_mask[nd]=(!empty_a(x))*2+(!empty_e(x)),pull(nd);}
	void del_mask(int x){int nd=node(x);if(nd)splay(nd),my_mask[nd]=0,pull(nd);}
	void ins_e(int x,int y){E.insert({x,y});add_mask(x);}
	void ins_a(int x,int y){A.insert({x,y});add_mask(x);}
	void del_e(int x,int y){E.erase({x,y});add_mask(x);}
	void del_a(int x,int y){A.erase({x,y});add_mask(x);}
	bool is_edge(int x,int y){return edg.find({x,y})!=edg.end();}
	bool is_arc(int x,int y){return A.find({x,y})!=A.end();}
	int sub_sz(int x){x=node(x);if(x)splay(x);return sz[x]/2+1;}
	void take_edges(int x,vector<pii>&ret){
		if(node(x)){
			x=node(x);
			while(1){
				splay(x);if(!(mask[x]&1))break;
				int y=Find(x,1);splay(y);
				assert(my_mask[y]&1);
				int X=my_edg[y].first;
				assert(!empty_e(X));
				int Y=E.lower_bound({X,0})->second;
				del_e(X,Y);del_e(Y,X);
				ret.pb({X,Y});
			}
		}else assert(empty_e(x));
	}
	pii take_arcs(int x,vector<pii>&ret){
		if(node(x)){
			x=node(x);
			while(1){
				splay(x);if(!(mask[x]&2))break;
				int y=Find(x,2);splay(y);
				assert(my_mask[y]&2);
				int X=my_edg[y].first;
				assert(!empty_a(X));
				int Y=A.lower_bound({X,0})->second;
				del_a(X,Y);del_a(Y,X);
				if(!con(X,Y))return {X,Y};
				else ret.pb({X,Y});
			}
		}else{
			while(!empty_a(x)){
				int y=A.lower_bound({x,0})->second;
				del_a(x,y);del_a(y,x);
				if(!con(x,y))return {x,y};
				else ret.pb({x,y});
			}
		}
		return {-1,-1};
	}
	void DelEdge(int x,int y){
		if(is_arc(x,y))del_a(x,y),del_a(y,x);
		else{
			if(E.find({x,y})!=E.end())del_e(x,y),del_e(y,x);
			del_mask(x);del_mask(y);
			fir(edg[{x,y}]);
			cut(edg[{x,y}]);edg.erase({x,y});
			cut(edg[{y,x}]);edg.erase({y,x});
			add_mask(x);add_mask(y);
		}
	}
	void AddEdge(int x,int y){
		if(con(x,y))ins_a(x,y),ins_a(y,x);
		else{
			del_mask(x);del_mask(y);
			int nx=node(x),ny=node(y);
			cng_rt(x);cng_rt(y);
			int a=edg[{x,y}]=New();my_edg[a]={x,y};
			int b=edg[{y,x}]=New();my_edg[b]={y,x};
			mrg(nx,a);mrg(a,ny);mrg(a,b);
			ins_e(x,y);ins_e(y,x);
		}
	}
};
struct HolmDeLichtenbergThorup{
	EulerTourTree ETT[L];
	HolmDeLichtenbergThorup(){}
	void init(){for(int i=0;i<L;i++)ETT[i].init();}
	void AddEdge(int u,int v){ETT[0].AddEdge(u,v);}
	void Replace(int u,int v,int lvl){
		pii repl={-1,-1};
		for(int i=lvl;i>=0;i--){
			int w=ETT[i].sub_sz(u)>ETT[i].sub_sz(v)?v:u;
			vector<pii> E;
			ETT[i].take_edges(w,E);
			for(auto p:E)ETT[i+1].AddEdge(p.first,p.second);
			E.clear();
			if(repl.first==-1)repl=ETT[i].take_arcs(w,E);
			for(auto p:E)ETT[i+1].AddEdge(p.first,p.second);
			if(repl.first!=-1)ETT[i].AddEdge(repl.first,repl.second);
		}
	}
	void DelEdge(int u,int v){
		if(ETT[0].is_edge(u,v)){
			int i;for(i=0;i<L;i++){
				if(ETT[i].is_edge(u,v))
					ETT[i].DelEdge(u,v);
				else break;
			}
			Replace(u,v,i-1);
		}else{
			for(int i=0;i<L;i++)
				if(ETT[i].is_arc(u,v))
					ETT[i].DelEdge(u,v);
		}
	}
	bool con(int u,int v){return ETT[0].con(u,v);}
}HDT;

void initialize(int n)
{
    HDT.init();
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++) HDT.AddEdge(i,j);
}
int hasEdge(int u, int v)
{
    u++, v++;
    if(u>v) swap(u,v);
    HDT.DelEdge(u,v);
    if(!HDT.con(u,v))
    {
        HDT.AddEdge(u,v);
        return 1;
    }
    return 0;
}

/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

game.cpp: In function 'void rot(int)':
game.cpp:40:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   40 |  if(~q)go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
      |  ^~
game.cpp:40:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   40 |  if(~q)go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
      |                   ^~
game.cpp:41:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   41 |  if(w)fa[w]=y;fa[y]=x;fa[x]=z;
      |  ^~
game.cpp:41:15: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   41 |  if(w)fa[w]=y;fa[y]=x;fa[x]=z;
      |               ^~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 27
• Subtask 3: 0 / 58