Submission #388133

#	Time	Username	Problem	Language	Result	Execution time	Memory
388133		nathanlee726	Construction of Highway (JOI18_construction)	C++14	100 / 100	362 ms	17604 KiB

construction

//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
struct link_cut_tree{
	struct SPLAY{
		int so[2],pa,v,si;
		bool tg;
		SPLAY():v(0),pa(0),tg(0),si(1){so[0]=so[1]=0;}
	}splay[100010];
	inline bool is_rt(int x){return splay[splay[x].pa].so[0]!=x&&splay[splay[x].pa].so[1]!=x;}
	inline void push(int x){
		if(splay[x].so[0])splay[splay[x].so[0]].v=splay[x].v;
		if(splay[x].so[1])splay[splay[x].so[1]].v=splay[x].v;
		if(splay[x].tg){
			if(splay[x].so[0])splay[splay[x].so[0]].tg^=1;
			if(splay[x].so[1])splay[splay[x].so[1]].tg^=1;
			swap(splay[x].so[0],splay[x].so[1]);
			splay[x].tg=0;
		}
	}
	void push_all(int x){
		if(!is_rt(x))push_all(splay[x].pa);
		push(x);
	}
	inline void upd(int x){
		splay[x].si=1;
		if(splay[x].so[0])splay[x].si+=splay[splay[x].so[0]].si;
		if(splay[x].so[1])splay[x].si+=splay[splay[x].so[1]].si;
	}
	inline void rotate(int x){
		int y=splay[x].pa,z=splay[y].pa,d=splay[y].so[1]==x;
		splay[x].pa=z;
		if(!is_rt(y))splay[z].so[splay[z].so[1]==y]=x;
		splay[splay[x].so[1^d]].pa=y;
		splay[y].so[d]=splay[x].so[1^d];
		splay[x].so[1^d]=y;
		splay[y].pa=x;
		upd(y);
		upd(x);
	}
	inline void Splay(int x){
		push_all(x);
		while(!is_rt(x)){
			int y=splay[x].pa;
			if(!is_rt(y)){
				int z=splay[y].pa;
				if((splay[y].so[0]==x)^(splay[z].so[0]==y))rotate(x);
				else rotate(y); 
			}
			rotate(x);
		}
	}
	inline vector<pii> access(int x,int vl){
		int la=0;
		vector<pii> re;
		while(x){
			Splay(x);
			splay[x].so[1]=0;
			upd(x);
			re.pb({splay[x].v,splay[x].si});
			splay[x].so[1]=la;
			splay[la].pa=x;
			upd(x);
			la=x;
			x=splay[x].pa;
		}
		splay[la].v=vl;
		return re;
	}
	inline void link(int x,int y){
		splay[y].pa=x;
	} 
}LCT;
vector<int> ve;
map<int,int> m;
int a[100010],balbit[100010];
void ADD(int x,int v){
	for(;x<=100001;x+=(x&(-x)))balbit[x]+=v;
}
int QRY(int x){
	int re=0;
	for(;x>0;x-=(x&(-x)))re+=balbit[x];
	return re;
}
signed main(){
	IOS();
	int n;
	cin>>n;
	F(n)cin>>a[i],ve.pb(a[i]);
	sort(all(ve));
	ve.resize(unique(all(ve))-ve.begin());
	F(sz(ve))m[ve[i]]=i+1;
	F(n)a[i]=m[a[i]];
	LCT.splay[1].v=a[0];
	F(n-1){
		int x,y;
		cin>>x>>y;
		vector<pii> tmp;
		tmp=LCT.access(x,a[y-1]);
		int ans=0;
		for(pii pi:tmp){
			ans+=pi.Y*QRY(pi.X-1);
			bug(pi.X,pi.Y);
			ADD(pi.X,pi.Y);
		}
		for(pii pi:tmp){
			ADD(pi.X,-pi.Y);
		}
		LCT.splay[y].v=a[y-1];
		LCT.link(x,y);
		cout<<ans<<endl;
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In constructor 'link_cut_tree::SPLAY::SPLAY()':
construction.cpp:72:16: warning: 'link_cut_tree::SPLAY::v' will be initialized after [-Wreorder]
   72 |   int so[2],pa,v,si;
      |                ^
construction.cpp:72:13: warning:   'long long int link_cut_tree::SPLAY::pa' [-Wreorder]
   72 |   int so[2],pa,v,si;
      |             ^~
construction.cpp:74:3: warning:   when initialized here [-Wreorder]
   74 |   SPLAY():v(0),pa(0),tg(0),si(1){so[0]=so[1]=0;}
      |   ^~~~~
construction.cpp:73:8: warning: 'link_cut_tree::SPLAY::tg' will be initialized after [-Wreorder]
   73 |   bool tg;
      |        ^~
construction.cpp:72:18: warning:   'long long int link_cut_tree::SPLAY::si' [-Wreorder]
   72 |   int so[2],pa,v,si;
      |                  ^~
construction.cpp:74:3: warning:   when initialized here [-Wreorder]
   74 |   SPLAY():v(0),pa(0),tg(0),si(1){so[0]=so[1]=0;}
      |   ^~~~~

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