Submission #201150

#	Time	Username	Problem	Language	Result	Execution time	Memory
201150		forelax	Min-max tree (BOI18_minmaxtree)	C++17	0 / 100	502 ms	23916 KiB

minmaxtree

#include<bits/stdc++.h>
using namespace std;
#define LG 20
struct node{
	vector<int> sparseTable;
	vector<int> neighbours;
	int parent;
	int depth;
	bool built;
	int unionPointer;
	int minQueryInd;
	int maxQueryInd;
	bool isEdgeUsed;
};
vector<node> nodes;
struct query{
	int ind,a,b,c;
};
vector<query> minQ,maxQ;
int n,k;
string s;
vector<int> queryValue;
vector<vector<pair<int,int> > > queryEdge;
vector<bool> isQueryActive;
vector<int> activeDegree;
vector<int> toProcess;
void build(int ind);
int lca(int a,int b);
int unionTop(int ind){return nodes[ind].unionPointer==ind?ind:nodes[ind].unionPointer=unionTop(nodes[ind].unionPointer);}
int main(){
	cin>>n;
	nodes.resize(n,{{},{},0,0,false,0,-1,-1,false});
	for(int i = 1,a,b ; i < n ; i ++){
		cin>>a>>b;--a;--b;
		nodes[a].neighbours.push_back(b);
		nodes[b].neighbours.push_back(a);
	}
	build(0);
	cin>>k;
	queryValue.resize(k);
	for(int i = 0,a,b,c ; i < k ; i ++){
		cin>>s>>a>>b>>c;
		if(s=="m")
			minQ.push_back({i,--a,--b,c});
		else
			maxQ.push_back({i,--a,--b,c});
		queryValue[i]=c;
	}
	sort(minQ.begin(),minQ.end(),[](const query& a,const query& b){return a.c>b.c;});
	sort(maxQ.begin(),maxQ.end(),[](const query& a,const query& b){return a.c<b.c;});
	for(int i = 0 ; i < n ; i ++)nodes[i].unionPointer=i;
	for(query q:minQ){
		int l=lca(q.a,q.b);
		while((q.a=unionTop(q.a))!=unionTop(l)){
			nodes[q.a].minQueryInd=q.ind;
			nodes[q.a].unionPointer=unionTop(nodes[q.a].parent);
		}
		while((q.b=unionTop(q.b))!=unionTop(l)){
			nodes[q.b].minQueryInd=q.ind;
			nodes[q.b].unionPointer=unionTop(nodes[q.b].parent);
		}
	}
	for(int i = 0 ; i < n ; i ++)nodes[i].unionPointer=i;
	for(query q:maxQ){
		int l=lca(q.a,q.b);
		while((q.a=unionTop(q.a))!=unionTop(l)){
			nodes[q.a].maxQueryInd=q.ind;
			nodes[q.a].unionPointer=unionTop(nodes[q.a].parent);
		}
		while((q.b=unionTop(q.b))!=unionTop(l)){
			nodes[q.b].maxQueryInd=q.ind;
			nodes[q.b].unionPointer=unionTop(nodes[q.b].parent);
		}
	}
	queryEdge.resize(k);
	isQueryActive.resize(k,false);
	activeDegree.resize(k);
	for(int i = 1 ; i < n ; i ++){
		if(nodes[i].minQueryInd!=-1){if(nodes[i].maxQueryInd!=-1){
			queryEdge[nodes[i].minQueryInd].push_back({nodes[i].maxQueryInd,i});
			queryEdge[nodes[i].maxQueryInd].push_back({nodes[i].minQueryInd,i});
			activeDegree[nodes[i].minQueryInd]++;
			activeDegree[nodes[i].maxQueryInd]++;
		}else{
			if(!isQueryActive[nodes[i].minQueryInd]){
				isQueryActive[nodes[i].minQueryInd]=true;
				nodes[i].isEdgeUsed=true;
				toProcess.push_back(nodes[i].minQueryInd);
				cout<<i+1<<" "<<nodes[i].parent+1<<" "<<queryValue[nodes[i].minQueryInd]<<endl;
			}
		}}else{if(nodes[i].maxQueryInd!=-1){
			if(!isQueryActive[nodes[i].maxQueryInd]){
				isQueryActive[nodes[i].maxQueryInd]=true;
				nodes[i].isEdgeUsed=true;
				toProcess.push_back(nodes[i].maxQueryInd);
				cout<<i+1<<" "<<nodes[i].parent+1<<" "<<queryValue[nodes[i].maxQueryInd]<<endl;
			}
		}else{
			cout<<i+1<<" "<<nodes[i].parent+1<<" "<<0<<endl;
			nodes[i].isEdgeUsed=true;
		}}
	}
	for(int i = 0 ; i < k ; i ++){
		if(isQueryActive[i]||activeDegree[i]>1)continue;
		isQueryActive[i]=true;
		nodes[queryEdge[i][0].second].isEdgeUsed=true;
		toProcess.push_back(i);
		cout<<queryEdge[i][0].second+1<<" "<<nodes[queryEdge[i][0].second].parent+1<<" "<<queryValue[i]<<endl;
	}
	vector<bool> isQueryProcessed(k);
	for(int i=0 ; i<k ; ){
		int ind;
		if(toProcess.size()){
			ind=toProcess.back();toProcess.pop_back();
		}else{
			if(isQueryProcessed[i]){i++;continue;}
			ind=i++;
			int nodeInd;
			for(pair<int,int> linkedQuery:queryEdge[ind]){
				if(nodes[linkedQuery.second].isEdgeUsed)continue;
				nodeInd=linkedQuery.second;
				break;
			}
			isQueryActive[ind]=true;
			nodes[nodeInd].isEdgeUsed=true;
			cout<<nodeInd+1<<" "<<nodes[nodeInd].parent+1<<" "<<queryValue[ind]<<endl;
		}
		isQueryProcessed[ind]=true;
		for(pair<int,int> linkedQuery:queryEdge[ind]){
			if(isQueryActive[linkedQuery.first])continue;
			if(--activeDegree[linkedQuery.first]==1){
				isQueryActive[linkedQuery.first]=true;
				nodes[linkedQuery.second].isEdgeUsed=true;
				toProcess.push_back(linkedQuery.first);
				cout<<linkedQuery.second+1<<" "<<nodes[linkedQuery.second].parent+1<<" "<<queryValue[linkedQuery.first]<<endl;
			}
		}
	}
}
void build(int ind){
	nodes[ind].depth=nodes[ nodes[ind].parent ].depth + 1;
	nodes[ind].built=true;
	nodes[ind].sparseTable.resize(LG, nodes[ind].parent);
	for(int i = 1 ; i < LG ; i ++)
		nodes[ind].sparseTable[i]=nodes[ nodes[ind].sparseTable[i-1] ].sparseTable[i-1];
	for(int neighbour:nodes[ind].neighbours){
		if(nodes[neighbour].built)continue;
		nodes[neighbour].parent=ind;
		build(neighbour);
	}
}
int lca(int a,int b){
	if(nodes[a].depth<nodes[b].depth)swap(a,b);
	for(int i = LG -1,h ; i >= 0 ; i --)if(nodes[ h=nodes[a].sparseTable[i] ].depth>=nodes[b].depth)a=h;
	if(a==b)return a;
	for(int i = LG-1,h,g ; i >= 0 ; i --)
		if((h=nodes[a].sparseTable[i])!=(g=nodes[b].sparseTable[i])) a=h,b=g;
	return nodes[a].parent;
}

Compilation message (stderr)

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:118:8: warning: 'nodeInd' may be used uninitialized in this function [-Wmaybe-uninitialized]
    int nodeInd;
        ^~~~~~~

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