oj.uz

Submission #73953

# Submission time Handle Problem Language Result Execution time Memory
73953 2018-08-29T10:33:06 Z zscoder Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 542 ms 63160 KB 
#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
		{
			auto it = G[labels[i].fi].lower_bound(mp(labels[i].se,-100));
			if(it!=G[labels[i].fi].end()&&it->fi==labels[i].se)
			{
				visited[labels[i].se]=1;
				visited[labels[i].fi]=1;
				ans[it->se] = L[it->se];
				ans[i] = R[i];
			}
			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();
		//cerr<<"CLEAR "<<u<<'\n';
		while(!G[u].empty())
		{
			ii V=(*G[u].begin());
			int v=V.fi; int lab=V.se;
			//cerr<<u<<' '<<v<<' '<<lab<<'\n';
			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);
			assert(h2[u]>=h2[v]);
			//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] = R[i];
	}
	for(int i=1;i<n;i++)
	{
		cout<<st[0][i]+1<<' '<<i+1<<' '<<ans[i]<<'\n';
	}
}

Compilation message

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;
       ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11132 KB Output is correct
2 Correct 13 ms 11132 KB Output is correct
3 Correct 12 ms 11272 KB Output is correct
4 Correct 12 ms 11272 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 26440 KB Output is correct
2 Correct 383 ms 26440 KB Output is correct
3 Correct 311 ms 26440 KB Output is correct
4 Correct 352 ms 27280 KB Output is correct
5 Correct 301 ms 27280 KB Output is correct
6 Correct 400 ms 27280 KB Output is correct
7 Correct 262 ms 27280 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 27280 KB Output is correct
2 Correct 180 ms 27280 KB Output is correct
3 Correct 237 ms 27280 KB Output is correct
4 Correct 214 ms 27280 KB Output is correct
5 Correct 193 ms 27280 KB Output is correct
6 Correct 304 ms 27280 KB Output is correct
7 Correct 235 ms 27280 KB Output is correct
8 Correct 216 ms 27280 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11132 KB Output is correct
2 Correct 13 ms 11132 KB Output is correct
3 Correct 12 ms 11272 KB Output is correct
4 Correct 12 ms 11272 KB Output is correct
5 Correct 448 ms 26440 KB Output is correct
6 Correct 383 ms 26440 KB Output is correct
7 Correct 311 ms 26440 KB Output is correct
8 Correct 352 ms 27280 KB Output is correct
9 Correct 301 ms 27280 KB Output is correct
10 Correct 400 ms 27280 KB Output is correct
11 Correct 262 ms 27280 KB Output is correct
12 Correct 165 ms 27280 KB Output is correct
13 Correct 180 ms 27280 KB Output is correct
14 Correct 237 ms 27280 KB Output is correct
15 Correct 214 ms 27280 KB Output is correct
16 Correct 193 ms 27280 KB Output is correct
17 Correct 304 ms 27280 KB Output is correct
18 Correct 235 ms 27280 KB Output is correct
19 Correct 216 ms 27280 KB Output is correct
20 Correct 440 ms 29328 KB Output is correct
21 Correct 347 ms 29508 KB Output is correct
22 Correct 376 ms 31696 KB Output is correct
23 Correct 359 ms 34028 KB Output is correct
24 Correct 507 ms 44300 KB Output is correct
25 Correct 542 ms 46604 KB Output is correct
26 Correct 386 ms 47456 KB Output is correct
27 Correct 468 ms 49592 KB Output is correct
28 Correct 476 ms 49592 KB Output is correct
29 Correct 412 ms 51344 KB Output is correct
30 Correct 340 ms 52008 KB Output is correct
31 Correct 385 ms 54268 KB Output is correct
32 Correct 392 ms 57828 KB Output is correct
33 Correct 342 ms 58600 KB Output is correct
34 Correct 374 ms 60768 KB Output is correct
35 Correct 402 ms 63160 KB Output is correct