oj.uz

Submission #201165

# Submission time Handle Problem Language Result Execution time Memory
201165 2020-02-09T13:52:41 Z forelax Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 435 ms 26600 KB 
#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(){
	ios::sync_with_stdio(false);
	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);
	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;
			}
		}}
	}
	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=-1;
			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){
				int nodeInd=-1;
				if(!nodes[linkedQuery.second].isEdgeUsed)nodeInd=linkedQuery.second;
				else for(pair<int,int> secondLink:queryEdge[linkedQuery.first]){
					if(nodes[secondLink.second].isEdgeUsed)continue;
					nodeInd=secondLink.second;
					break;
				}
				isQueryActive[linkedQuery.first]=true;
				nodes[nodeInd].isEdgeUsed=true;
				toProcess.push_back(linkedQuery.first);
				cout<<nodeInd+1<<" "<<nodes[nodeInd].parent+1<<" "<<queryValue[linkedQuery.first]<<endl;
			}
		}
	}
	for(int i = 1 ; i < n ; i ++){
		if(!nodes[i].isEdgeUsed){
			if(nodes[i].maxQueryInd==-1&&nodes[i].minQueryInd==-1)
				cout<<i+1<<" "<<nodes[i].parent+1<<" "<<0<<endl;
			else if(nodes[i].maxQueryInd==-1)
				cout<<i+1<<" "<<nodes[i].parent+1<<" "<<queryValue[nodes[i].minQueryInd]<<endl;
			else
				cout<<i+1<<" "<<nodes[i].parent+1<<" "<<queryValue[nodes[i].maxQueryInd]<<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;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 21352 KB Output is correct
2 Correct 325 ms 19820 KB Output is correct
3 Correct 333 ms 19948 KB Output is correct
4 Correct 351 ms 21864 KB Output is correct
5 Correct 337 ms 19948 KB Output is correct
6 Correct 359 ms 20456 KB Output is correct
7 Correct 320 ms 19816 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 17236 KB Output is correct
2 Correct 284 ms 17524 KB Output is correct
3 Correct 305 ms 18204 KB Output is correct
4 Correct 299 ms 18816 KB Output is correct
5 Correct 296 ms 17596 KB Output is correct
6 Correct 290 ms 17992 KB Output is correct
7 Correct 272 ms 17652 KB Output is correct
8 Correct 275 ms 17620 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 394 ms 21352 KB Output is correct
6 Correct 325 ms 19820 KB Output is correct
7 Correct 333 ms 19948 KB Output is correct
8 Correct 351 ms 21864 KB Output is correct
9 Correct 337 ms 19948 KB Output is correct
10 Correct 359 ms 20456 KB Output is correct
11 Correct 320 ms 19816 KB Output is correct
12 Correct 260 ms 17236 KB Output is correct
13 Correct 284 ms 17524 KB Output is correct
14 Correct 305 ms 18204 KB Output is correct
15 Correct 299 ms 18816 KB Output is correct
16 Correct 296 ms 17596 KB Output is correct
17 Correct 290 ms 17992 KB Output is correct
18 Correct 272 ms 17652 KB Output is correct
19 Correct 275 ms 17620 KB Output is correct
20 Correct 340 ms 23092 KB Output is correct
21 Correct 299 ms 21488 KB Output is correct
22 Correct 315 ms 21612 KB Output is correct
23 Correct 331 ms 21992 KB Output is correct
24 Correct 435 ms 26244 KB Output is correct
25 Correct 400 ms 26600 KB Output is correct
26 Correct 401 ms 26092 KB Output is correct
27 Correct 407 ms 25900 KB Output is correct
28 Correct 390 ms 23952 KB Output is correct
29 Correct 365 ms 23960 KB Output is correct
30 Correct 346 ms 22892 KB Output is correct
31 Correct 350 ms 23096 KB Output is correct
32 Correct 376 ms 24016 KB Output is correct
33 Correct 367 ms 23356 KB Output is correct
34 Correct 344 ms 23196 KB Output is correct
35 Correct 343 ms 22740 KB Output is correct