oj.uz

Submission #73098

# Submission time Handle Problem Language Result Execution time Memory
73098 2018-08-27T16:09:58 Z khohko Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 495 ms 43180 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
using namespace std;
#define ll int
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e9+100))
#define MX ((ll)(7e4+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;
vector<ll> v[ARRS];
vector<ll> g[ARRS];
set<ll> *st[ARRS];
ll pas[ARRS];
ll mn[ARRS];
ll mx[ARRS];
ll pr[ARRS];
map<ll,ll> mp;


void go(ll x,ll p){
	pr[x]=p;
	st[x]=new set<ll>();
	for(auto k:g[x])
		st[x]->insert(k);

	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());
	if(mx[x]==MAX)mx[x]=0;
}

map<ll,ll> f;

ll mv(ll x){
	if(x==-1)return 0;
	if(x==0)return 1;
	//if(f[x]==2)return 0;
	//if(!f[x]){
		//f[x]=1;
	if(!f[mn[x]]){
		f[mn[x]]=1;
		if(mv(mp[mn[x]])){
			pas[x]=mn[x];
			mp[mn[x]]=x;
			return 1;
		}
	}
	//}
//	f[x]=2;
	if(!f[mx[x]]){
		f[mx[x]]=1;
		if(mv(mp[mx[x]])){
			pas[x]=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;
	ll te=q;
	while(q--){
		char ch;
		ll l,r,x;
		cin>>ch>>l>>r>>x;
		x++;
		if(ch=='m'){
			g[l].pb(-x);
			g[r].pb(-x);
		}
		else {
			g[l].pb(x);
			g[r].pb(x);
		}
	}

	go(1,0);

	mp[0]=-1;
	ll p=0;
	for(int i=2; i<=n; i++){
		f.clear();
		p+=mv(i);
	}
	//cout<<p<<" "<<te<<endl;

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

Compilation message

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:97:5: warning: unused variable 'te' [-Wunused-variable]
  ll te=q;
     ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 13 ms 10012 KB Output is correct
3 Correct 11 ms 10012 KB Output is correct
4 Correct 11 ms 10012 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 37184 KB Output is correct
2 Correct 450 ms 41732 KB Output is correct
3 Correct 409 ms 41732 KB Output is correct
4 Correct 407 ms 41732 KB Output is correct
5 Correct 456 ms 41732 KB Output is correct
6 Correct 369 ms 41732 KB Output is correct
7 Correct 398 ms 41732 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 41732 KB Output is correct
2 Correct 332 ms 41732 KB Output is correct
3 Correct 305 ms 41732 KB Output is correct
4 Correct 317 ms 41732 KB Output is correct
5 Correct 290 ms 41732 KB Output is correct
6 Correct 363 ms 41732 KB Output is correct
7 Correct 345 ms 41732 KB Output is correct
8 Correct 387 ms 41732 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 13 ms 10012 KB Output is correct
3 Correct 11 ms 10012 KB Output is correct
4 Correct 11 ms 10012 KB Output is correct
5 Correct 386 ms 37184 KB Output is correct
6 Correct 450 ms 41732 KB Output is correct
7 Correct 409 ms 41732 KB Output is correct
8 Correct 407 ms 41732 KB Output is correct
9 Correct 456 ms 41732 KB Output is correct
10 Correct 369 ms 41732 KB Output is correct
11 Correct 398 ms 41732 KB Output is correct
12 Correct 299 ms 41732 KB Output is correct
13 Correct 332 ms 41732 KB Output is correct
14 Correct 305 ms 41732 KB Output is correct
15 Correct 317 ms 41732 KB Output is correct
16 Correct 290 ms 41732 KB Output is correct
17 Correct 363 ms 41732 KB Output is correct
18 Correct 345 ms 41732 KB Output is correct
19 Correct 387 ms 41732 KB Output is correct
20 Correct 455 ms 43180 KB Output is correct
21 Correct 427 ms 43180 KB Output is correct
22 Correct 437 ms 43180 KB Output is correct
23 Correct 484 ms 43180 KB Output is correct
24 Correct 495 ms 43180 KB Output is correct
25 Correct 419 ms 43180 KB Output is correct
26 Correct 436 ms 43180 KB Output is correct
27 Correct 471 ms 43180 KB Output is correct
28 Correct 386 ms 43180 KB Output is correct
29 Correct 452 ms 43180 KB Output is correct
30 Correct 450 ms 43180 KB Output is correct
31 Correct 436 ms 43180 KB Output is correct
32 Correct 435 ms 43180 KB Output is correct
33 Correct 417 ms 43180 KB Output is correct
34 Correct 407 ms 43180 KB Output is correct
35 Correct 419 ms 43180 KB Output is correct