Submission #573060

#	Time	Username	Problem	Language	Result	Execution time	Memory
573060		SilentVisitor	Min-max tree (BOI18_minmaxtree)	C++17	7 / 100	4 ms	4308 KiB

minmaxtree

/*
     author : SilentVisitor
     created on 12.01.22 12.52 A.M. 
*/ 
#include<bits/stdc++.h> 
using namespace std;                                               
#ifdef _DEBUG 
#include "algo/debug.h" 
#else
#define debug(...) 69420 
#endif
#define deb(...) union 

#define ll long long
#define i64 int64_t 

#define ff first 
#define ss second

#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define sz(s) s.size()
vector<char> data = {'a', 'e', 'i', 'o', 'u'}; 
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }

const int N = 10101; 
char C[N]; 
vector<int> vec,g[N],vmn[N],vmx[N];
vector<pair<int,pair<int,int>>> G[N];
set<int> smn[N],smx[N];
int n, m, rt, a[N], W[N], U[N], V[N], vis[N]; 
map<pair<int, int>, int> mark; 

void solve(){ 
	 cin >> n; 
	 for(int i = 1; i < n; i += 1){
	 	  int u, v; 
	 	  cin >> u >> v;  
          g[u].push_back(v); 
          g[v].push_back(u); 
	 }
	 cin >> m; 
	 for(int i = 0; i < m; i += 1){
          cin >> C[i] >> U[i] >> V[i] >> W[i];
	      vec.push_back(W[i]); 
	 }
     sort(all(vec)); 
     for(int i = 0; i < m; i += 1){
     	  W[i] = lower_bound(all(vec), W[i]) - vec.begin()+1; 
     	  int u = U[i], v = V[i], w = W[i]; 
     	  if(C[i] == 'M'){
     	  	   vmx[u].push_back(w); 
     	  	   vmx[v].push_back(w); 
     	  }
     	  else {
     	  	   vmn[u].push_back(w); 
     	  	   vmn[v].push_back(w); 
     	  }
     }
     function<void(int, int, int, int)> out = [&](int s, int t, int u, int v) {
     	 int res = 0; 
     	 cout<<s<<" "<<t<<" ";
	     if(u==0 || v==0) res=max(u,v);
	     else res=v;
	     res = max(res, 1); 
	     cout<<vec[res-1];
	     cout<<endl;
     }; 
     function<void(int, int)> dfs = [&](int u, int p){
     	   int x=0;
	for(auto v : g[u]){
		if(v==p) continue ;
		dfs(v,u);
		if(smn[v].size()+smx[v].size()>smn[x].size()+smx[x].size()){
			x=v;
		}
	}
	swap(smn[u],smn[x]);
	swap(smx[u],smx[x]);
	for(auto x : vmn[u]){
		if(smn[u].find(x)!=smn[u].end()) smn[u].erase(x);
		else smn[u].insert(x);
	}
	for(auto x : vmx[u]){
		if(smx[u].find(x)!=smx[u].end()) smx[u].erase(x);
		else smx[u].insert(x);
	}
	for(auto v : g[u]){
		if(v==p || v==x) continue ;
		for(auto x : smn[v]){
			if(smn[u].find(x)!=smn[u].end()) smn[u].erase(x);
			else smn[u].insert(x);
		}
		for(auto x : smx[v]){
			if(smx[u].find(x)!=smx[u].end()) smx[u].erase(x);
			else smx[u].insert(x);
		}
	}
	if(u==1) return ;
	int l=0,r=0;
	if(smn[u].size()) l=*smn[u].rbegin();
	if(smx[u].size()) r=*smx[u].begin();
	G[l].push_back({r,{u,p}});
	G[r].push_back({l,{u,p}});
     }; 
     function<void(int, int)> dfs1 = [&](int u, int p){
           vis[u] = 1; 
           for(auto v : G[u]){
		       if(vis[v.ff]){
			       if(p!=v.ff) rt=v.ff;
			          continue;
		   }
		   dfs1(v.ff,u);
	     }
     }; 
     function<void(int)> dfs2 = [&](int u) {
          vis[u] = 2; 
          for(auto p : G[u]){
          	  int v = p.ff, s = p.ss.ff, t = p.ss.ss; 
          	  if(!mark[make_pair(s, t)]){
          	  	  mark[make_pair(s, t)] = 1; 
          	  	  out(s, t, u, v); 
          	  }
          	  if(vis[v] < 2)
          	  	  dfs2(v); 
          }
     }; 
     function<void(int)> exact = [&](int node) {
           rt = 0; 
           dfs1(node, node); 
           dfs2(rt); 
     }; 
     dfs(1, 1); 
     for(int i = 0; i < m+1; i += 1){
     	  if(!vis[i])
                exact(i); 
          }
}
main(void){
       ios::sync_with_stdio(false); 
       cin.tie(0); 
       cout.tie(0);
       solve(); 
       return 0; 
}

Compilation message (stderr)

minmaxtree.cpp:140:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  140 | main(void){
      | ^~~~

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