oj.uz

답안 #244302

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244302 2020-07-03T14:58:51 Z TadijaSebez Treasure Hunt (CEOI11_tre) C++11
100 / 100
 3510 ms 93572 KB 
#include <bits/stdc++.h>
//#include "treasure.h"
#include "treinc.h"
using namespace std;
#define pb push_back

const int N=400050*2;
int go[N][2],fa[N],sz[N],fir[N],las[N],my_sz[N],tag[N],tsz;
void pull(int x){sz[x]=sz[go[x][0]]+my_sz[x]+sz[go[x][1]];}
void upd(int x){swap(go[x][0],go[x][1]);swap(fir[x],las[x]);tag[x]^=1;}
void push(int x){if(tag[x])upd(go[x][0]),upd(go[x][1]),tag[x]=0;}
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 cl(int x){if(~pd(x))cl(fa[x]);push(x);}
void splay(int x){for(cl(x);~pd(x);rot(x))if(~pd(fa[x]))rot(pd(x)==pd(fa[x])?fa[x]:x);}
void access(int x){for(splay(x),go[x][1]=0,pull(x);fa[x];rot(x))splay(fa[x]),go[fa[x]][1]=x,pull(fa[x]);}
void make_rt(int x){access(x);upd(x);}
void take_path(int x,int y){make_rt(x);access(y);}
int Get(int x,int k){
	push(x);
	if(sz[go[x][0]]>k)return Get(go[x][0],k);
	k-=sz[go[x][0]];
	if(my_sz[x]>k)return x;
	k-=my_sz[x];
	return Get(go[x][1],k);
}
void cut(int u,int v){
	make_rt(u);access(v);
	go[v][0]=0;fa[u]=0;
	pull(v);
}
int LCA(int u,int v){
	make_rt(1);
	access(u);
	access(v);
	splay(u);
	if(!fa[u])return u;
	return fa[u];
}
void P(int u){
	if(!u)return;
	push(u);
	P(go[u][0]);
	printf("(%i - %i) ",fir[u],las[u]);
	P(go[u][1]);
}

int n;
int dwn[N],up[N];
map<pair<int,int>,int> nodes;
int AddNode(int l,int r){
	tsz++;
	fir[tsz]=l;las[tsz]=r;my_sz[tsz]=r-l+1;pull(tsz);
	nodes[{l,r}]=tsz;
	return tsz;
}
void init(){
	//tsz++;fir[tsz]=las[tsz]=my_sz[tsz]=1;pull(tsz);nodes[{1,1}]=tsz;
	AddNode(1,1);
	n=1;
}

int GetNode(int u){
	auto it=nodes.upper_bound({u+1,0});
	it--;
	return it->second;
}
void Extract(int u){
	//make_rt(1);
	int nd=GetNode(u);
	splay(nd);
	if(fir[nd]==las[nd])return;
	assert(fir[nd]<las[nd]);
	if(u==las[nd])return;
	//if(fir[nd]>las[nd])swap(fir[nd],las[nd]);
	//printf("Extract %i from (%i %i)\n",u,fir[nd],las[nd]);
	nodes.erase({fir[nd],las[nd]});
	int U=up[nd],D=dwn[nd];
	//printf("U (%i-%i) D (%i-%i)\n",fir[U],las[U],fir[D],las[D]);
	int F=fir[nd],L=las[nd];
	access(U);
	splay(nd);
	fa[nd]=0;
	//cut(U,nd);
	//if(D)cut(D,nd);
	vector<int> nds;
	nds.pb(AddNode(F,u));
	//splay(nd);
	nds.pb(nd);fir[nd]=u+1;las[nd]=L;my_sz[nd]=L-u;pull(nd);nodes[{u+1,L}]=nd;
	//if(L!=u)nds.pb(AddNode(u+1,L));
	int tmp=U;
	for(int i:nds){
		//printf("%i do %i\n",fir[i],las[i]);
		up[i]=tmp;
		fa[i]=tmp;
		dwn[tmp]=i;
		tmp=i;
	}
	/*dwn[tmp]=D;
	if(D){
		make_rt(D);
		fa[D]=up[D]=tmp;
	}*/
}

void path(int u,int len){
	//tsz++;fir[tsz]=n+1;las[tsz]=n+len;my_sz[tsz]=len;pull(tsz);nodes[{n+1,n+len}]=tsz;
	int now=AddNode(n+1,n+len);
	Extract(u);
	fa[now]=up[now]=GetNode(u);
	n+=len;
}

/*void FixLCA(int u,int v){
	int lca=LCA(u,v);
	//printf("FIX (%i %i) for (%i %i) ^ (%i %i)\n",fir[lca],las[lca],fir[u],las[u],fir[v],las[v]);
	splay(lca);
	if(fir[lca]==las[lca])return;
	Extract(las[lca]-1);
}*/
int dig(int u,int v){
	Extract(u);Extract(v);
	int nu=GetNode(u);
	int nv=GetNode(v);
	//printf("%i %i\n",nu,nv);
	//FixLCA(nu,nv);
	int lca=LCA(nu,nv);
	take_path(nu,nv);
	splay(lca);
	int ssz=sz[lca]-(my_sz[lca]-1);
	int need=(ssz-1)/2;
	if(sz[go[lca][0]]+1<=need)need+=my_sz[lca]-1;
	//splay(nu);
	//printf("ssz %i pre %i\n",ssz,need);
	//P(nu);printf("\n");
	int mid_node=Get(lca,need);
	splay(mid_node);
	int ost=need-sz[go[mid_node][0]];
	int ans;
	if(fir[mid_node]<las[mid_node])ans=fir[mid_node]+ost;
	else ans=fir[mid_node]-ost;
	make_rt(1);
	return ans;
}

//---------------------//
/*
int main(){
	int q;scanf("%i",&q);
	while(q--){
		char c;int u,v;
		scanf("\n%c %i %i",&c,&u,&v);
		if(c=='i')init();
		else if(c=='p')path(u,v);
		else printf("%i\n",dig(u,v));
		//for(int i=1;i<=tsz;i++)printf("(%i %i)\n",fir[i],las[i]);
	}
	return 0;
}
*/
//---------------------//

Compilation message

tre.cpp: In function 'void rot(int)':
tre.cpp:15:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(~q)go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
  ^~
tre.cpp:15:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(~q)go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
                   ^~
tre.cpp:16:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(w)fa[w]=y;fa[y]=x;fa[x]=z;
  ^~
tre.cpp:16:15: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(w)fa[w]=y;fa[y]=x;fa[x]=z;
               ^~
tre.cpp: In function 'void Extract(int)':
tre.cpp:83:15: warning: unused variable 'D' [-Wunused-variable]
  int U=up[nd],D=dwn[nd];
               ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1024 KB Output is correct
2 Correct 17 ms 1024 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1054 ms 50816 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2919 ms 49552 KB Output is correct
2 Correct 2431 ms 54972 KB Output is correct
3 Correct 1945 ms 54952 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1239 ms 34048 KB Output is correct
2 Correct 1694 ms 35892 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2923 ms 72048 KB Output is correct
2 Correct 1924 ms 86560 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1652 ms 48352 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3510 ms 88712 KB Output is correct
2 Correct 445 ms 57456 KB Output is correct
3 Correct 3118 ms 90392 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2403 ms 93572 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2347 ms 93568 KB Output is correct