Submission #530466

#TimeUsernameProblemLanguageResultExecution timeMemory
530466Koosha_mvMin-max tree (BOI18_minmaxtree)C++14
0 / 100
68 ms24832 KiB
#include <bits/stdc++.h> using namespace std; #define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl #define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl #define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define all(v) v.begin(),v.end() #define bit(n,k) (((n)>>(k))&1) #define Add(x,y) x=(x+y)%mod #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first const int N=1e5+99; int n,m,rt,a[N],W[N],U[N],V[N],vis[N]; 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]; map<pair<int,int>,int> mark; void output(int s,int t,int u,int v){ int res; cout<<s<<" "<<t<<" "; if(u==0 || v==0) res=max(u,v); else res=v; maxm(res,1); cout<<vec[res-1]; cout<<endl; } void 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 || 1) 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(); //cout<<p<<" "<<u<<" -> "<<l<<" "<<r<<endl; G[l].pb({r,{u,p}}); G[r].pb({l,{u,p}}); } void dfs1(int u,int p){ vis[u]=1; for(auto v : G[u]){ if(vis[v.F]){ if(p!=v.F) rt=v.F; continue ; } dfs1(v.F,u); } } void dfs2(int u){ vis[u]=2; for(auto p : G[u]){ int v=p.F,s=p.S.F,t=p.S.S; if(!mark[mp(s,t)]){ //cout<<u<<" "<<v<<endl; mark[mp(s,t)]=1; output(s,t,u,v); } if(vis[v]<2){ dfs2(v); } } } void solve(int u){ rt=0; dfs1(u,u); dfs2(rt); } int main(){ ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n; f(i,1,n){ int u,v; cin>>u>>v; g[u].pb(v); g[v].pb(u); } cin>>m; f(i,0,m){ cin>>C[i]>>U[i]>>V[i]>>W[i]; vec.pb(W[i]); } sort(all(vec)); f(i,0,m){ 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].pb(w); vmx[v].pb(w); } else{ vmn[u].pb(w); vmn[v].pb(w); } } //dfs(1,1); f(i,0,m+1){ if(!vis[i]){ solve(i); } } } /* 4 1 2 2 3 3 4 3 M 1 4 10 m 1 4 0 M 2 3 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...