Submission #69883

#	Time	Username	Problem	Language	Result	Execution time	Memory
69883		khohko	Min-max tree (BOI18_minmaxtree)	C++17	29 / 100	477 ms	48948 KiB

minmaxtree

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e12+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e5+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;

ll n,m,q;
set<ll> *st[ARRS];
vector<ll> v[ARRS];
vector<ll> g[ARRS];
ll mn[ARRS];
ll mx[ARRS];
ll pr[ARRS];

void go(ll x,ll p){
	pr[x]=p;
	st[x]=new set<ll>;
	for(auto y:g[x])
		st[x]->insert(y);
	//cout<<x<<endl;
	for(auto y:v[x]){
		if(y==p)continue;
		go(y,x);
		if(st[x]->size()<st[y]->size())swap(st[x],st[y]);
		for(auto k:*st[y]){
			if(st[x]->find(k)!=st[x]->end())
				st[x]->erase(k);
			else st[x]->insert(k);
		}
	}

	st[x]->insert(0);
	st[x]->insert(MAX);

	mx[x]=*st[x]->upper_bound(0);
	mn[x]=-(*st[x]->begin());
	//mx[x]=max(-1ll,mx[x]);
	if(mx[x]==MAX)mx[x]=-1;
	if(mn[x]==0)mn[x]=-1;
}

ll f[ARRS];
ll pas[ARRS];
map<ll,ll> mp;


bool mv(ll x){
	if(x==-1)return 0;
	if(!x)return 1;
	if(f[x])return 0;
	f[x]=1;
	if(mx[x]&&mv(mp[mx[x]])){
		mp[mx[x]]=x;
		return 1;
	}
	return 0;
}

int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=0; i<n-1; i++){
		ll k,p;
		cin>>k>>p;
		v[k].pb(p);
		v[p].pb(k);
	}
	cin>>q;
	for(int i=0; i<q; i++){
		char ch;
		ll x,y,k;
		cin>>ch>>x>>y>>k;
		k++;
		if(ch=='m'){
			g[x].pb(-k);
			g[y].pb(-k);
		}
		else {
			g[x].pb(k);
			g[y].pb(k);
		}
	}
	go(1,-1);

	mp[-1]=-1;
	for(int i=2; i<=n; i++){
		ll x=i;
		if(mn[x]&&mv(mp[mn[x]])){
			mp[mn[x]]=x;
		}
		else if(mx[x]&&mv(mp[mx[x]])){
			f[x]=1;
			mp[mx[x]]=x;
		}
	}

	for(auto x:mp)
		pas[mp[x.fr]]=x.fr;

	for(int i=2; i<=n; i++){
		if(!pas[i])pas[i]=max(0ll,mn[i]);
		cout<<pr[i]<<" "<<i<<" "<<pas[i]-1<<endl;
	}
}

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