Submission #73941

#	Time	Username	Problem	Language	Result	Execution time	Memory
73941		zscoder	Min-max tree (BOI18_minmaxtree)	C++17	22 / 100	531 ms	33172 KiB

minmaxtree

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<int> adj[77777];
int siz[77777];
int in[77777];
int h[77777];
int nxt[77777];
int out[77777];
int timer;
const int LG = 17;
int st[LG][77777];

void dfs_siz(int u, int p)
{
	siz[u]=1;
	if(adj[u][0]==p&&adj[u].size()>1)
	{
		swap(adj[u][0],adj[u][1]);
	}
	for(auto &v:adj[u])
	{
		if(v==p) continue;
		dfs_siz(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[adj[u][0]])
		{
			swap(v,adj[u][0]);
		}
	}
}

int L[77777];
int R[77777];
const int INF = int(1e9)+8;

void dfs_hld(int u, int p)
{
	in[u]=timer++; st[0][u]=p;
	for(int v:adj[u])
	{
		if(v==p) continue;
		nxt[v] = (v==adj[u][0]?nxt[u]:v);
		h[v]=h[u]+1; L[v]=-INF; R[v]=INF;
		dfs_hld(v,u);
	}
	out[u]=timer;
}

int ans[77777];

int go_up(int u, int k)
{
	for(int i=LG-1;i>=0;i--)
	{
		//cerr<<u<<' '<<k<<' '<<i<<' '<<st[1][2]<<'\n';
		if(k&(1<<i)) u=st[i][u];
	}
	return u;
}

int lca(int u, int v)
{
	if(h[u]>h[v]) swap(u,v);
	for(int i=LG-1;i>=0;i--)
	{
		if(st[i][v]!=-1&&h[st[i][v]]>=h[u])
		{
			v=st[i][v];
		}
	}
	if(u==v) return u;
	for(int i=LG-1;i>=0;i--)
	{
		if(st[i][v]!=-1&&st[i][v]!=st[i][u])
		{
			v=st[i][v]; u=st[i][u];
		}
	}
	return st[0][u];
}

int type[77777];
int queries[77777];

struct node
{
	int query[2];
	int lazy[2];
	node()
	{
		memset(query,-1,sizeof(query)); memset(lazy,-1,sizeof(lazy));
	}
};

node T[77778*4];

void push(int id, int l, int r)
{
	for(int z=0;z<2;z++)
	{
		if(T[id].lazy[z]!=-1)
		{
			T[id].query[z]=T[id].lazy[z];
			if(r-l>=2)
			{
				T[id*2].lazy[z]=T[id*2+1].lazy[z]=T[id].lazy[z];
			}
			T[id].lazy[z]=-1;
		}
	}
}

void update(int id, int l, int r, int ql, int qr, int ty, int val)
{
	push(id,l,r);
	if(ql>=r||l>=qr) return ;
	if(ql<=l&&r<=qr)
	{
		T[id].lazy[ty] = val;
		push(id,l,r); return ;
	}
	int mid=(l+r)>>1;
	update(id*2,l,mid,ql,qr,ty,val); update(id*2+1,mid,r,ql,qr,ty,val);
}

pair<int,int> query(int id, int l, int r, int pos)
{
	push(id,l,r);
	if(pos>=r||pos<l) return mp(-1,-1);
	if(r-l<2) return mp(T[id].query[0],T[id].query[1]);
	int mid=(l+r)>>1;
	return max(query(id*2,l,mid,pos),query(id*2+1,mid,r,pos));
}

int n; 

void update_up(int u, int v, int ty, int val)
{
	//cerr<<"UPDATE "<<u<<' '<<v<<' '<<ty<<' '<<val<<'\n';
	int cur = u;
	while(h[nxt[cur]]>=h[v])
	{
		update(1,0,n,in[nxt[cur]],in[cur]+1,ty,val);
		cur=st[0][nxt[cur]];
	}
	if(h[cur]>=h[v])
	{
		update(1,0,n,in[v],in[cur]+1,ty,val);
	}
}

void update_path(int u, int v, int ty, int val)
{
	int lc=lca(u,v);
	//cerr<<"UPDATE PATH "<<u<<' '<<v<<' '<<lc<<'\n';
	if(h[lc]<h[u]) 
	{
		int uup = go_up(u, h[u]-h[lc]-1);
		update_up(u,uup,ty,val);
	}
	if(h[lc]<h[v])
	{
		int vup = go_up(v, h[v]-h[lc]-1);
		update_up(v,vup,ty,val);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n; nxt[0]=0;
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	dfs_siz(0,-1); dfs_hld(0,-1);
	for(int i=1;i<LG;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(st[i-1][j]==-1) st[i][j]=-1;
			else st[i][j]=st[i-1][st[i-1][j]];
		}
	}
	int q; cin>>q;
	vector<pair<ii,ii> > querymax;
	vector<pair<ii,ii> > querymin;
	for(int i=0;i<q;i++)
	{
		char c; cin>>c;
		int u,v; cin>>u>>v; u--; v--;
		int val; cin>>val;
		if(c=='M')
		{
			querymax.pb(mp(mp(val,i),mp(u,v)));
		}
		else
		{
			querymin.pb(mp(mp(val,i),mp(u,v)));
		}
		queries[i]=val; type[i] = (c=='M'?1:0);
	}
	sort(querymax.rbegin(),querymax.rend());
	sort(querymin.begin(),querymin.end());
	for(auto query:querymax)
	{
		int val = query.fi.fi; int lab = query.fi.se; int u = query.se.fi; int v = query.se.se;
		update_path(u,v,1,lab);
	}
	for(auto query:querymin)
	{
		int val = query.fi.fi; int lab = query.fi.se; int u = query.se.fi; int v = query.se.se;
		update_path(u,v,0,lab);
	}
	for(int i=1;i<n;i++)
	{
		ii labels = query(1,0,n,in[i]);
		if(labels.fi!=-1) L[i] = queries[labels.fi];
		if(labels.se!=-1) R[i] = queries[labels.se];
		//cerr<<st[0][i]+1<<' '<<i+1<<' '<<L[i]<<' '<<R[i]<<'\n';
		cout<<st[0][i]+1<<' '<<i+1<<' '<<R[i]<<'\n';
	}
}	

Compilation message (stderr)

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:224:7: warning: unused variable 'val' [-Wunused-variable]
   int val = query.fi.fi; int lab = query.fi.se; int u = query.se.fi; int v = query.se.se;
       ^~~
minmaxtree.cpp:229:7: warning: unused variable 'val' [-Wunused-variable]
   int val = query.fi.fi; int lab = query.fi.se; int u = query.se.fi; int v = query.se.se;
       ^~~

• Subtask 1: 0 / 7
• Subtask 2: 22 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42