제출 #365919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365919		kshitij_sodani	Min-max tree (BOI18_minmaxtree)	C++14	7 / 100	489 ms	75632 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 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];
vector<pair<llo,llo>> adj3[200001];
llo vis3[200001];
llo vis4[200001];
pair<llo,llo> mm;
llo mm2;
map<llo,llo> zz;
void dfs3(int no,int par=-1){
	vis3[no]=1;
	for(auto j:adj3[no]){
		if(vis3[j.a]==0){
			dfs3(j.a,no);
		}
		else if(j.a!=par){
			mm={j.a,no};
			mm2=j.b;
		}
	}
}
llo vis5[200001];
void dfs4(int no,int par=-1){
	vis4[no]=1;
	for(auto j:adj3[no]){
		/*if(j.a==mm.b and no==mm.a){
			continue;
		}*/
		if(vis4[j.a]==0){
			vis5[j.b]=1;	
			cout<<j.b+1<<" "<<par2[j.b]+1<<" "<<zz[j.a]<<endl;
			dfs4(j.a,no);
		}
		else if(j.a!=par){
		
		}

	}
}
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);
	
	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); 
 	llo ind=n;
 	map<llo,llo> yy;
 	
 	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);
 		}
 		if(rr[i]!=-1){
 			adj2[i].insert(yy[rr[i]]);
 			adj2[yy[rr[i]]].insert(i);
 		}
 		if(ll[i]==-1 and rr[i]==-1){
 			cout<<i+1<<" "<<par2[i]+1<<" "<<1<<endl;
 			ans++;
 		}
 	//	cout<<ll[i]<<":"<<rr[i]<<endl;
 	}

 	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});
 			}
 		}
 	}

 	while(true){
 		if(cot.size()==0 and cot2.size()==0){
 			break;
 		}
 		
 		if(cot.size()>0){
 			pair<llo,llo> no=*(cot.begin());
 			if(no.a==1){
 				vis5[no.b]=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]--;
 				cout<<no.b+1<<" "<<par2[no.b]+1<<" "<<zz[nn]<<endl;
 				continue;
 			}
 		}
 	
		break;
 	}
 	for(auto j:cot){
 		adj3[yy[ll[j.b]]].pb({yy[rr[j.b]],j.b});
 		adj3[yy[rr[j.b]]].pb({yy[ll[j.b]],j.b});
 		//cout<<yy[ll[j.b]]<<","<<yy[rr[j.b]]<<endl;
 	}
 //	cout<<(cot.size())<<endl;
 	for(int i=1;i<=2*n;i++){
 		if(vis3[i]==0){
 			if(adj3[i].size()>0){
 				dfs3(i);
 			
 				dfs4(mm.a);
 			//	cout<<11<<endl;
 				cout<<mm2+1<<" "<<par2[mm2]+1<<" "<<zz[mm.a]<<endl;
 				vis5[mm2]=1;
 			}

 		}
 	}
 	for(int i=1;i<n;i++){
 		if(vis5[i]==0){
 			cout<<i+1<<" "<<par2[i]+1<<" "<<ll[i]<<endl;
 		}
 	}




 
	return 0;
}

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

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

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