oj.uz

Submission #69835

# Submission time Handle Problem Language Result Execution time Memory
69835 2018-08-21T15:19:29 Z khohko Min-max tree (BOI18_minmaxtree) C++17
29 / 100
 469 ms 45712 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)(1e6+100))
#define ARRS ((ll)(1e5+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]=0;
}

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;
	//	f[x]=1;
		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[0]=-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]=mn[i];
		cout<<pr[i]<<" "<<i<<" "<<pas[i]-1<<endl;
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 9 ms 5220 KB Output is correct
4 Correct 7 ms 5396 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 32836 KB Output is correct
2 Correct 469 ms 39660 KB Output is correct
3 Correct 412 ms 39660 KB Output is correct
4 Correct 431 ms 39660 KB Output is correct
5 Correct 403 ms 40892 KB Output is correct
6 Correct 431 ms 42620 KB Output is correct
7 Correct 395 ms 42632 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 42632 KB Output is correct
2 Correct 282 ms 42632 KB Output is correct
3 Correct 233 ms 42632 KB Output is correct
4 Correct 263 ms 42632 KB Output is correct
5 Correct 271 ms 42632 KB Output is correct
6 Correct 327 ms 44036 KB Output is correct
7 Correct 265 ms 44536 KB Output is correct
8 Incorrect 268 ms 45712 KB Output isn't correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 9 ms 5220 KB Output is correct
4 Correct 7 ms 5396 KB Output is correct
5 Correct 429 ms 32836 KB Output is correct
6 Correct 469 ms 39660 KB Output is correct
7 Correct 412 ms 39660 KB Output is correct
8 Correct 431 ms 39660 KB Output is correct
9 Correct 403 ms 40892 KB Output is correct
10 Correct 431 ms 42620 KB Output is correct
11 Correct 395 ms 42632 KB Output is correct
12 Correct 264 ms 42632 KB Output is correct
13 Correct 282 ms 42632 KB Output is correct
14 Correct 233 ms 42632 KB Output is correct
15 Correct 263 ms 42632 KB Output is correct
16 Correct 271 ms 42632 KB Output is correct
17 Correct 327 ms 44036 KB Output is correct
18 Correct 265 ms 44536 KB Output is correct
19 Incorrect 268 ms 45712 KB Output isn't correct