제출 #365858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365858		kshitij_sodani	Min-max tree (BOI18_minmaxtree)	C++14	0 / 100	492 ms	93932 KiB

minmaxtree

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,k;
vector<llo> pre[100001];
set<llo> cur[100001];
vector<llo> adj[100001];
vector<llo> pre2[100001];
llo ll[100001];
llo rr[100001];
llo par2[100001];
llo vis[100001];
llo vis2[300001];
set<llo> adj2[300001];
llo match[300001];
llo dfs4(llo no){
	if(vis2[no]){
		return 0;
	}
	vis2[no]=1;
	for(auto k:adj2[no]){
		if(match[k]==-1 or dfs4(match[k])){
			match[k]=no;
			return 1;
		}
	}
	return 0;

}
void dfs3(llo no,llo par=-1){
	par2[no]=par;
	for(auto j:adj[no]){
		if(j!=par){
			dfs3(j,no);
		}
	}
}
llo dfs(llo no,llo par=-1){

	llo ma=-1;
	llo ind=-1;
	par2[no]=par;
	vector<llo> ss;
	for(auto j:adj[no]){
		if(j!=par){
			llo x=dfs(j,no);
			ss.pb(x);
			//cout<<no<<":"<<j<<":"<<x<<endl;
			if((llo)cur[x].size()>ma){
				ma=cur[x].size();
				ind=x;
			}
		}
	}
	if(ma==-1){
		//cout<<no<<":"<<endl;
		ind=no;
	}

	for(auto j:ss){
		if(j!=ind){
			for(auto j:cur[j]){
				if(cur[ind].find(j)!=cur[ind].end()){
					cur[ind].erase(j);
					continue;
				}
				cur[ind].insert(j);
			}
			cur[j].clear();
		}
	}


	for(auto j:pre[no]){
		if(cur[ind].find(j)!=cur[ind].end()){
			cur[ind].erase(j);
			continue;
		}
		cur[ind].insert(j);
	}
	if(par!=-1){
		//cout<<no+1<<" "<<par+1<<" ";
		if(cur[ind].size()){
			rr[no]=(*(cur[ind].begin()));
		//	cout<<(*(cur[ind].begin()))<<endl;
		}//
		else{
			rr[no]=-1;
		//	cout<<1<<endl;
		}
	}
	return ind;

}

llo dfs2(llo no,llo par=-1){

	llo ma=-1;
	llo ind=-1;
	vector<llo> ss;
	for(auto j:adj[no]){
		if(j!=par){
			llo x=dfs2(j,no);
			ss.pb(x);
			//cout<<no<<":"<<j<<":"<<x<<endl;
			if((llo)cur[x].size()>ma){
				ma=cur[x].size();
				ind=x;
			}
		}
	}
	if(ma==-1){
		//cout<<no<<":"<<endl;
		ind=no;
	}

	for(auto j:ss){
		if(j!=ind){
			for(auto j:cur[j]){
				if(cur[ind].find(j)!=cur[ind].end()){
					cur[ind].erase(j);
					continue;
				}
				cur[ind].insert(j);
			}
			cur[j].clear();
		}
	}


	for(auto j:pre2[no]){
		if(cur[ind].find(-j)!=cur[ind].end()){
			cur[ind].erase(-j);
			continue;
		}
		cur[ind].insert(-j);
	}
	if(par!=-1){
		//cout<<no+1<<" "<<par+1<<" ";
		if(cur[ind].size()){
			ll[no]=-(*(cur[ind].begin()));
		//	cout<<(*(cur[ind].begin()))<<endl;
		}//
		else{
			ll[no]=-1;
		//	cout<<1<<endl;
		}
	}
	return ind;

}
llo co[300001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n;
	for(llo i=0;i<n-1;i++){
		llo aa,bb,cc;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	} 
	cin>>k;
	set<llo> xx;

	//dfs3(0);
		/*for(int i=0;i<n;i++){
		cout<<par2[i]<<"::";
	}
	cout<<endl;*/
	llo ans=0;
 	for(llo i=0;i<k;i++){
 		char s;
 		cin>>s;
 		llo aa,bb,cc;
 		cin>>aa>>bb>>cc;
 		aa--;
 		bb--;
 		/*if(bb==par2[aa]){
 			swap(aa,bb);
 		}
 		if(aa==par2[bb]){
 			cout<<aa+1<<" "<<bb+1<<" "<<cc<<endl;
 			vis[bb]=1;
 			ans++;
 			continue;
 		}*/
 		xx.insert(cc);
 		if(s=='M'){
 			pre[aa].pb(cc);
 			pre[bb].pb(cc);
 		}
 		else{
 			pre2[aa].pb(cc);
 			pre2[bb].pb(cc);
 		}
 	}
 	dfs(0);	
 	for(llo i=0;i<n;i++){
 		cur[i].clear();
 	}

 	dfs2(0);
/* 	for(llo i=1;i<n;i++){
 		cout<<ll[i]<<":"<<rr[i]<<endl;
 	}*/

 
 	llo ind=n;
 	map<llo,llo> yy;
 	map<llo,llo> zz;
 	for(auto i:xx){
 		yy[i]=ind;
 		zz[ind]=i;
 		ind++;
 	}
 	
 	for(llo i=1;i<n;i++){
 		if(vis[i]==1){
 			continue;
 		}
 		if(ll[i]!=-1){
 			adj2[i].insert(yy[ll[i]]);
 			adj2[yy[ll[i]]].insert(i);
 			//cout<<i<<":"<<ll[i]<<endl;
 		}
 		if(rr[i]!=-1){
 			adj2[i].insert(yy[rr[i]]);
 			adj2[yy[rr[i]]].insert(i);
 		//	cout<<i<<":"<<rr[i]<<endl;
 		}
 		if(ll[i]==-1 and rr[i]==-1){
 			cout<<i+1<<" "<<par2[i]+1<<" "<<1<<endl;
 			ans++;
 		}
 	}
/* 	for(int i=0;i<=2*n;i++){
 		match[i]=-1;
 	}
 	for(int i=1;i<n;i++){
 		for(int j=0;j<=2*n;j++){
 			vis[j]=0;
 		}
 		dfs4(i);
 	}
 	map<int,int> ans2;
 	for(int i=0;i<=2*n;i++){
 		if(match[i]!=-1){
 			ans2[match[i]]=zz[i];
 		}
 		cout<<i<<":"<<match[i]<<endl;
 	}
 	for(int i=1;i<n;i++){
 		cout<<ans2[i]<<":";
 		if(adj2[i].size()){
 			cout<<i+1<<" "<<par2[i]+1<<" "<<ans2[i]<<endl;
 		}
 	}
 	cout<<endl;



 	return 0;*/
 	set<pair<llo,llo>> cot;
 	set<pair<llo,llo>> cot2;
 	for(llo i=1;i<=200000;i++){
 		if(adj2[i].size()>0){
 			co[i]=adj2[i].size();
 			if(i<n){
 				cot.insert({adj2[i].size(),i});
 			}
 			else{
 				cot2.insert({adj2[i].size(),i});
 			}
 		}
 	}
 /*	for(int i=1;i<n;i++){
 		cout<<ll[i]<<":"<<rr[i]<<endl;
 	}*/
 	//return 0;
 		/*for(auto j:cot2){
 					cout<<zz[j.b]<<",,"<<j.a<<endl;
 				}
 				for(auto j:cot){
 					cout<<j.b<<",,,"<<j.a<<endl;
 				}*/
 	 while(true){
 		if(cot.size()==0 and cot2.size()==0){
 			break;
 		}
 		if(cot2.size()>0){
 			pair<llo,llo> no=*(cot2.begin());
 			if(no.a==1){
 				llo nn=*(adj2[no.b].begin());
 				cot2.erase({no});
 				co[no.b]--;

 				cot.erase({co[nn],nn});
 				adj2[nn].erase(no.b);
 				adj2[no.b].erase(nn);
 				for(auto j:adj2[nn]){

 					cot2.erase({co[j],j});
 					adj2[j].erase(nn);
 					co[j]--;
 					if(co[j]>0){
 						cot2.insert({co[j],j});
 					}	
 				}
 				co[nn]--;
 				/*if(co[nn]>0){
 					cot.insert({co[nn],nn});
 				}*/
 				ans++;
 				cout<<nn+1<<" "<<par2[nn]+1<<" "<<zz[no.b]<<endl;
 				continue;
 			}
 		}
		break;
 	}
 	int ccd=0;
 		for(auto j:cot2){
 			if(j.a==1){
 				ccd++;
 			}
 		}
 		if(ccd>1){
 			while(true){
 				continue;
 			}
 		}

 		

 	while(true){
 		if(cot.size()==0 and cot2.size()==0){
 			break;
 		}

 		ans++;

 		if(cot.size()>0){
 			pair<llo,llo> no=*(cot.begin());
 			if(no.a==1){
 				llo nn=*(adj2[no.b].begin());
 				cot.erase({no});
 				co[no.b]--;

 				cot2.erase({co[nn],nn});
 				adj2[nn].erase(no.b);
 				adj2[no.b].erase(nn);
 				for(auto j:adj2[nn]){
 					cot.erase({co[j],j});
 					adj2[j].erase(nn);
 					co[j]--;
 					if(co[j]>0){
 						cot.insert({co[j],j});
 					}	
 				}

 				co[nn]--;
 				/*if(co[nn]>0){
 					cot2.insert({co[nn],nn});
 				}*/
 				cout<<no.b+1<<" "<<par2[no.b]+1<<" "<<zz[nn]<<endl;
 				/*for(auto j:cot2){
 					cout<<zz[j.b]<<",,"<<j.a<<endl;
 				}
 				for(auto j:cot){
 					cout<<j.b<<",,,"<<j.a<<endl;
 				}
 				*/
 				continue;
 			}
 		}
 		if(cot2.size()>0){
 			pair<llo,llo> no=*(cot2.begin());
 			if(no.a==1){
 				llo nn=*(adj2[no.b].begin());
 				cot2.erase({no});
 				co[no.b]--;

 				cot.erase({co[nn],nn});
 				adj2[nn].erase(no.b);
 				adj2[no.b].erase(nn);
 				for(auto j:adj2[nn]){

 					cot2.erase({co[j],j});
 					adj2[j].erase(nn);
 					co[j]--;
 					if(co[j]>0){
 						cot2.insert({co[j],j});
 					}	
 				}
 				co[nn]--;
 				/*if(co[nn]>0){
 					cot.insert({co[nn],nn});
 				}*/
 				cout<<nn+1<<" "<<par2[nn]+1<<" "<<zz[no.b]<<endl;
 			/*	for(auto j:cot2){
 					cout<<zz[j.b]<<",,"<<j.a<<endl;
 				}
 				for(auto j:cot){
 					cout<<j.b<<",,,"<<j.a<<endl;
 				}*/
 				

 				continue;
 			}
 		}
 		



 		pair<llo,llo> no=*(cot2.begin());
 		llo nn=*(adj2[no.b].begin());
		cot2.erase({no});
		co[no.b]--;
		cot.insert({co[no.b],no.b});

		cot.erase({co[nn],nn});

		 	adj2[nn].erase(no.b);
 			adj2[no.b].erase(nn);
		for(auto j:adj2[nn]){
			cot2.erase({co[j],j});
			adj2[j].erase(nn);
			co[j]--;
			if(co[j]>0){
 				cot2.insert({co[j],j});
 			}	
		}

		for(auto j:adj2[no.b]){
			cot.erase({co[j],j});
			adj2[j].erase(no.b);
			co[j]--;
			if(co[j]>0){
 				cot.insert({co[j],j});
 			}	
		}

		co[nn]--;
		/*if(co[nn]>0){
			cot.insert({co[nn],nn});
		}*/
		cout<<nn+1<<" "<<par2[nn]+1<<" "<<zz[no.b]<<endl;
		
		continue;
 	}
/* 	if(ans!=n-1){
 		while(true){
 			continue;
 		}
 	}
*/



 
	return 0;
}

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

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:165:13: warning: unused variable 'cc' [-Wunused-variable]
  165 |   llo aa,bb,cc;
      |             ^~

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