Submission #110227

#	Time	Username	Problem	Language	Result	Execution time	Memory
110227		Angelos	Min-max tree (BOI18_minmaxtree)	C++11	22 / 100	584 ms	31116 KiB

minmaxtree

#include <bits/stdc++.h>
#define pb push_back
#define mpf make_pair
#define MAXN 100100
#define MAXD 20
#define MAXINT 1000000000
#define MININT -1
#define l (2*cur)
#define r ((2*cur)+1)
#define mid (a+b)/2

using namespace std;
int N;
vector<int> adj[MAXN] , edgeidx[MAXN];
int treesz[MAXN] , depth[MAXN] , lca[MAXN][MAXD] , edgebelow[MAXN] , edgeabove[MAXN] , edgetoseg[MAXN] , segtoedge[MAXN];
int tree[4*MAXN][2] , lazy[4*MAXN][2] , fn[MAXN][2] , ee[MAXN][2] , topchain[MAXN];
map <int,bool> mp;

void segupd(int cur , int a , int b , int i , int j , int val , int t){
        if(a > j || b < i) return;
	//cout << cur << " " << a << " " << b << " " << i << " " << j << " " << val << " " << t << endl;
	
	if(lazy[cur][t] != 0){
		if(a == b){
			int u = lazy[cur][t];
			if(t == 0) tree[cur][t] = max(tree[cur][t] , u);
			else tree[cur][t] = min(tree[cur][t] , u);
			goto exit;
		}
		int u = lazy[cur][t];
		if(lazy[l][t] == 0) lazy[l][t] = u;
		else if(t == 0) lazy[l][t] = max(lazy[l][t] , u);
		else lazy[l][t] = min(lazy[l][t] , u);
			
		if(lazy[r][t] == 0) lazy[r][t] = u;
		else if(t == 0) lazy[r][t] = max(lazy[r][t] , u);
		else lazy[r][t] = min(lazy[r][t] , u);
		
				
		lazy[cur][t] = 0;
	}
	exit:
	if(a >= i && b <= j){
		tree[cur][t] = (t == 0) ? max(tree[cur][t] , val) : min(tree[cur][t] , val);
		lazy[cur][t] = val;
			
		return;
	}

	segupd(l , a , mid , i , j , val , t);
	segupd(r , mid + 1 , b , i , j , val , t);
	tree[cur][t] = (t == 0) ? max(tree[l][t] , tree[r][t]) : min(tree[l][t] , tree[r][t]);
}


void segupd(int i , int j , int val , int t){
        segupd(1 , 0 , N-2 , i , j , val , t);
}
                                            
void segpush(int cur , int a , int b , int t){
	if(lazy[cur][t] != 0){
		if(a == b){
			if(t == 0) tree[cur][t] = max(tree[cur][t] , lazy[cur][t]);
			else tree[cur][t] = min(tree[cur][t] , lazy[cur][t]);
			
			fn[segtoedge[a]][t] = tree[cur][t];
			return;
		}
		int u = lazy[cur][t];
		if(lazy[l][t] == 0) lazy[l][t] = u;
		else if(t == 0) lazy[l][t] = max(lazy[l][t] , u);
		else lazy[l][t] = min(lazy[l][t] , u);
			
		if(lazy[r][t] == 0) lazy[r][t] = u;
		else if(t == 0) lazy[r][t] = max(lazy[r][t] , u);
		else lazy[r][t] = min(lazy[r][t] , u);
		
				
		lazy[cur][t] = 0;
	}
	
	if(a == b){
		fn[segtoedge[a]][t] = tree[cur][t];
		return;
	}
		

	segpush(l , a , mid , t);
	segpush(r , mid + 1 , b , t);	
}
                                          
void dfsForSize(int cur , int pr){
	treesz[cur]++;
	for(int i=0; i<adj[cur].size(); i++){
		int nxt = adj[cur][i];
		if(nxt == pr) continue;
		
		lca[nxt][0] = cur;		
		depth[nxt] = depth[cur] + 1;
		edgeabove[nxt] = edgeidx[cur][i];		
		dfsForSize(nxt , cur);
		treesz[cur] += treesz[nxt];
	}
	
}

void initLCA(){
        for(int d = 1; d<MAXD; d++)
		for(int i=0; i<N; i++)
			lca[i][d] = lca[ lca[i][d-1] ][d-1];	
} 

void dfsForHLD(int cur , int topCh , int pr , int &segtreeidx , int idx){
	if(pr != -1){
		edgetoseg[ edgeidx[pr][idx] ] = segtreeidx;
		segtoedge[ segtreeidx++ ] = edgeidx[pr][idx];
	}
	topchain[cur] = topCh;
	
	int k = -1;
	for(int i=0; i<adj[cur].size(); i++){
		int nxt = adj[cur][i];
		if(nxt == pr) continue;
		if(k == -1 || treesz[ adj[cur][k] ] < treesz[ adj[cur][i] ]) k = i;
	}	
	
	if(k == -1) return;
	edgebelow[cur] = edgeidx[cur][k];
	dfsForHLD(adj[cur][k] , topCh , cur , segtreeidx , k);
			
	for(int i=0; i<adj[cur].size(); i++){
		int nxt = adj[cur][i];
		if(nxt == pr || i == k) continue;
		dfsForHLD(nxt , nxt , cur , segtreeidx , i);
	}
}

void initHLD(){
        dfsForSize(0 , -1);
	initLCA();
		         	
	int segtreeidx = 0;
	dfsForHLD(0 , 0 , -1 , segtreeidx , -1);	
}

int getLCA(int u , int v){
	if(depth[u] < depth[v]) swap(u,v);
	
	for(int d = MAXD-1; d>=0; d--)
		if(depth[u] - (1 << d) >= depth[v]) u = lca[u][d];
	
	for(int d=MAXD-1; d>=0; d--)
		if(lca[u][d] != lca[v][d]){ u = lca[u][d] , v = lca[v][d];}
	
	if(u != v){
		u = lca[u][0];
		v = lca[v][0];
	}
	
	return u;
}

void hld(int ch , int pr , int val , int t){
       
        while(ch != pr){
      		if(topchain[ch] == ch){
			segupd(edgetoseg[ edgeabove[ch] ] , edgetoseg[ edgeabove[ch] ] , val , t);
			ch = lca[ch][0]; 
		}
		else if(depth[ topchain[ch] ] > depth[pr] ){
			segupd(edgetoseg[ edgebelow[topchain[ch]] ] , edgetoseg[ edgeabove[ch] ] , val , t);
			ch = topchain[ch];
		}
		else{
			//cout << ch << " " << edgeabove[ch] << " + " << pr << " " << edgebelow[pr] << endl;
			//cout << edgetoseg[ edgeabove[ch] ] << " - " << edgetoseg[ edgebelow[pr] ] << endl;
			segupd(edgetoseg[ edgebelow[pr] ] , edgetoseg[ edgeabove[ch] ] , val , t);
			break; 			
		}
	}
}

void output(){
	for(int i=0; i<N-1; i++){
		cout << edgetoseg[i] << " " << edgeabove[i] << " " << edgebelow[i] << " " << endl;	
	}
	cout << endl;
	for(int i=0; i<N; i++){
		cout << treesz[i] << " " << depth[i] << " " << lca[i][0] << " " << topchain[i] << endl;
	}
	cout << endl;
	cout << endl;


}


int main(){
        std::cin >> N;

	for(int i=0; i<4*MAXN; i++) tree[i][1] = MAXINT , tree[i][0] = MININT;
	int rr = 0;
	for(int i=0; i<N-1; i++){
		int u,v; cin >> u >> v; u--;v--;
		ee[rr][0] = u + 1 , ee[rr++][1] = v + 1;
		adj[u].pb(v);
		adj[v].pb(u);
		edgeidx[u].pb(i);
		edgeidx[v].pb(i);
	}
	
	initHLD();
	//output();
	int Q; cin >> Q;
	while(Q--){
		char c; cin >> c;
		int u,v,w;cin >> u >> v >> w;u--;v--;
		//rr++;
		//ee[rr][0] = u , ee[rr++][1] = v;
		int pr = getLCA(u , v);
		//cout << "LCA " << pr << endl;
		int t;
		if(c == 'm') t = 0;
		else t = 1;
		hld(u , pr , w , t) , hld(v , pr,w,t);	
	}
	
	segpush(1 , 0 , N-2 , 0);
	segpush(1 , 0 , N-2 , 1);
	
	
	/*for(int i=0; i<N; i++)
		cout << i  << " " << fn[i][0] << " " << fn[i][1] << endl;
	
	cout << endl; cout << endl;*/
	//output();
	for(int i=0; i<N-1; i++)
		cout << ee[i][0] << " " << ee[i][1] << " "  << fn[i][1] << '\n';
	
		
	/*for(int i=0; i<N-1; i++){
		map<int,int>::iterator it;
		it = mp.find(fn[i][0]);
		if(it == mp.end()) mp[fn[i][0]] = 1;
		else mp[fn[i][0]]++;
		
		it = mp.find(fn[i][1]);
		if(it == mp.end()) mp[fn[i][1]] = 1;
		else mp[fn[i][1]]++;		
	}		      	
	for(int i=0; i<N-1; i++){
		cout << ee[i][0] << " " <<  ee[i][1] << " ";
		int u = fn[i][0] , v = fn[i][1];
		
		if(u == MININT && v == MAXINT) cout << "69" << endl;
		else if(u == MININT) {cout << v << endl; mp[v] = 0;}
		else if(v == MAXINT) {cout << u << endl; mp[u] = 0;}
		else if(mp[u] == 0) {cout << v << endl; mp[v] = 0;}
		else if(mp[v] == 0) {cout << u << endl; mp[u] = 0;}
		else if(mp[u] == 1) {cout << u << endl; mp[u] = 0;mp[v]--;}
	*/
	


	return 0;
}

Compilation message (stderr)

minmaxtree.cpp: In function 'void dfsForSize(int, int)':
minmaxtree.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[cur].size(); i++){
               ~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfsForHLD(int, int, int, int&, int)':
minmaxtree.cpp:121:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[cur].size(); i++){
               ~^~~~~~~~~~~~~~~~
minmaxtree.cpp:131:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<adj[cur].size(); i++){
               ~^~~~~~~~~~~~~~~~

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