oj.uz

Submission #530469

# Submission time Handle Problem Language Result Execution time Memory
530469 2022-02-25T12:34:55 Z Koosha_mv Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 307 ms 49464 KB 
#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) 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].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)]){
			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);
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19148 KB Output is correct
2 Correct 10 ms 19044 KB Output is correct
3 Correct 10 ms 19148 KB Output is correct
4 Correct 9 ms 19148 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 43876 KB Output is correct
2 Correct 273 ms 42356 KB Output is correct
3 Correct 268 ms 41816 KB Output is correct
4 Correct 260 ms 45484 KB Output is correct
5 Correct 252 ms 41488 KB Output is correct
6 Correct 267 ms 37184 KB Output is correct
7 Correct 239 ms 34768 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 32648 KB Output is correct
2 Correct 214 ms 32820 KB Output is correct
3 Correct 214 ms 39660 KB Output is correct
4 Correct 200 ms 43628 KB Output is correct
5 Correct 220 ms 33748 KB Output is correct
6 Correct 212 ms 34736 KB Output is correct
7 Correct 220 ms 32036 KB Output is correct
8 Correct 220 ms 32048 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19148 KB Output is correct
2 Correct 10 ms 19044 KB Output is correct
3 Correct 10 ms 19148 KB Output is correct
4 Correct 9 ms 19148 KB Output is correct
5 Correct 275 ms 43876 KB Output is correct
6 Correct 273 ms 42356 KB Output is correct
7 Correct 268 ms 41816 KB Output is correct
8 Correct 260 ms 45484 KB Output is correct
9 Correct 252 ms 41488 KB Output is correct
10 Correct 267 ms 37184 KB Output is correct
11 Correct 239 ms 34768 KB Output is correct
12 Correct 208 ms 32648 KB Output is correct
13 Correct 214 ms 32820 KB Output is correct
14 Correct 214 ms 39660 KB Output is correct
15 Correct 200 ms 43628 KB Output is correct
16 Correct 220 ms 33748 KB Output is correct
17 Correct 212 ms 34736 KB Output is correct
18 Correct 220 ms 32036 KB Output is correct
19 Correct 220 ms 32048 KB Output is correct
20 Correct 302 ms 44404 KB Output is correct
21 Correct 296 ms 42312 KB Output is correct
22 Correct 307 ms 43696 KB Output is correct
23 Correct 303 ms 42044 KB Output is correct
24 Correct 261 ms 44092 KB Output is correct
25 Correct 279 ms 49464 KB Output is correct
26 Correct 271 ms 47976 KB Output is correct
27 Correct 275 ms 43812 KB Output is correct
28 Correct 275 ms 38844 KB Output is correct
29 Correct 272 ms 39460 KB Output is correct
30 Correct 277 ms 39164 KB Output is correct
31 Correct 272 ms 39116 KB Output is correct
32 Correct 302 ms 39032 KB Output is correct
33 Correct 288 ms 40192 KB Output is correct
34 Correct 287 ms 39912 KB Output is correct
35 Correct 280 ms 37976 KB Output is correct