제출 #73947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73947		zscoder	Min-max tree (BOI18_minmaxtree)	C++17	22 / 100	406 ms	42824 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);
	}
}

ii labels[77777];
int par2[77777];
set<ii> G[77777];
bool visited[77777];
int h2[77777];
ii backedge;
int backedgelab;
int paredge[77777];

void dfs2(int u, int p)
{
	visited[u]=1;
	for(ii X:G[u])
	{
		int v=X.fi; int lab=X.se;
		if(v==p) continue;
		if(visited[v])
		{
			if(h2[v]<h2[u])
			{
				backedge=mp(u,v); //v is parent
				backedgelab=lab;
			}
		}
		else
		{
			paredge[v]=lab;
			par2[v]=u; h2[v]=h2[u]+1; ans[lab] = queries[v];
			dfs2(v,u);
		}
	}
}

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);
	}
	memset(ans,-1,sizeof(ans));
	for(int i=1;i<n;i++)
	{
		labels[i] = query(1,0,n,in[i]);
		if(labels[i].fi!=-1) L[i] = queries[labels[i].fi];
		if(labels[i].se!=-1) R[i] = queries[labels[i].se];
		//cerr<<st[0][i]+1<<' '<<i+1<<' '<<L[i]<<' '<<R[i]<<'\n';
		//cout<<st[0][i]+1<<' '<<i+1<<' '<<R[i]<<'\n';
	}
	for(int i=1;i<n;i++)
	{
		if(labels[i].fi==-1&&labels[i].se==-1) continue;
		//cerr<<i<<' '<<labels[i].fi<<' '<<labels[i].se<<'\n';
		if(labels[i].se==-1)
		{
			ans[i]=L[i]; visited[labels[i].fi]=1;
		}
		else if(labels[i].fi==-1)
		{
			ans[i]=R[i]; visited[labels[i].se]=1;
		}
		else
		{
			G[labels[i].fi].insert(mp(labels[i].se, i)); G[labels[i].se].insert(mp(labels[i].fi, i));
		}
	}
	queue<int> Q;
	for(int i=0;i<q;i++)
	{
		if(visited[i]) Q.push(i);
	}
	while(!Q.empty())
	{
		int u = Q.front(); Q.pop();
		while(!G[u].empty())
		{
			ii V=(*G[u].begin());
			int v=V.fi; int lab=V.se;
			if(ans[lab]==-1)
			{
				ans[lab] = queries[v];
			}
			G[v].erase(mp(u,lab));
			if(!visited[v]) 
			{
				Q.push(v); visited[v]=1;
			}
			G[u].erase(G[u].begin());
		}
	}
	for(int i=0;i<q;i++)
	{
		if(!visited[i])
		{
			backedge=mp(-1,-1);
			dfs2(i,-1);
			int u = backedge.fi; int v = backedge.se; 
			assert(u>=0);
			//u go up to v
			//paredge from u to root is flipped
			int cur = u;
			while(cur!=i)
			{
				ans[paredge[cur]] = queries[par2[cur]];
				cur=par2[cur];
			}			
			ans[backedgelab] = queries[u];
		}	
	}
	for(int i=1;i<n;i++)
	{
		if(ans[i]==-1) ans[i] = L[i];
	}
	for(int i=1;i<n;i++)
	{
		cout<<st[0][i]+1<<' '<<i+1<<' '<<ans[i]<<'\n';
	}
}	

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

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:257: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:262: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:321:29: warning: unused variable 'v' [-Wunused-variable]
    int u = backedge.fi; int v = backedge.se; 
                             ^

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