제출 #105342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105342		he_____he	Construction of Highway (JOI18_construction)	C++14	100 / 100	260 ms	7544 KiB

construction

#include<bits/stdc++.h>

#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

ll ans;
int n;
int ch[100005][2],fa[100005],siz[100005],val[100005],rev[100005],p[100005];
ll c[100005];
vector<pii> v;

int lowbit(int x){return x&(-x);}
void add(int x,int k){for(;x<=n;x+=lowbit(x))c[x]+=k;}
ll ask(int x){ll ret=0;for(;x;x-=lowbit(x))ret+=c[x];return ret;}
bool nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
bool son(int x){return ch[fa[x]][1]==x;}
void reverse(int x){rev[x]^=1,swap(ch[x][0],ch[x][1]);}
void pushdown(int x){if(rev[x])reverse(ch[x][0]),reverse(ch[x][1]),rev[x]=0;}
void update(int x){siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];}

void rotate(int x){
	int y=fa[x],z=fa[y],k=son(x),w=ch[x][!k];
	if(nroot(y)) ch[z][son(y)]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) fa[w]=y;
	fa[y]=x,fa[x]=z;
	if(!nroot(x)) val[x]=val[y];
	update(y),update(x);
}

void pushall(int x){
	if(nroot(x)) pushall(fa[x]);
	pushdown(x);
}

void splay(int x){
	pushall(x);
	while(nroot(x)){
		int y=fa[x];
		if(nroot(y)) rotate(son(x)==son(y)?y:x);
		rotate(x);
	}
}

void access(int x,int k=0){
	for(int y=0;x;x=fa[y=x]){
		splay(x);
		val[ch[x][1]]=val[x],ch[x][1]=y;
		update(x);
		if(k) ans+=1ll*(siz[x]-siz[ch[x][1]])*ask(val[x]-1);
		if(k) add(val[x],siz[x]-siz[ch[x][1]]),v.push_back(mp(val[x],siz[x]-siz[ch[x][1]]));
		if(k) val[x]=k;
	}
}

void makeroot(int x){access(x); splay(x); reverse(x);}

int main(){
	n=readint();
	for(int i=1;i<=n;i++) p[i]=val[i]=readint();
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++) val[i]=lower_bound(p+1,p+n+1,val[i])-p;
	for(int i=1;i<=n;i++) siz[i]=1;
	int x,y;
	for(int i=1;i<=n-1;i++){
		x=readint(); y=readint();
		ans=0;
//		cout<<"###########################"<<endl;
//		for(int j=1;j<=n;j++) cout<<j<<' '<<fa[j]<<' '<<ch[j][0]<<' '<<ch[j][1]<<' '<<val[j]<<' '<<siz[j]<<endl;
//		cout<<"###########################"<<endl;
		access(x,val[y]);
		printf("%lld\n",ans);
		fa[y]=x;
		for(int j=0;j<v.size();j++) add(v[j].fi,-v[j].se);
		v.clear();
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

construction.cpp: In function 'int main()':
construction.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<v.size();j++) add(v[j].fi,-v[j].se);
               ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84