oj.uz

Submission #73037

# Submission time Handle Problem Language Result Execution time Memory
73037 2018-08-27T14:10:10 Z khohko Min-max tree (BOI18_minmaxtree) C++17
29 / 100
 508 ms 45032 KB 
#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]=0;
	//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;
	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)
		if(x.fr>0)pas[x.sc]=x.fr;

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 10 ms 9960 KB Output is correct
3 Correct 12 ms 9960 KB Output is correct
4 Correct 12 ms 10188 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 40472 KB Output is correct
2 Correct 428 ms 45032 KB Output is correct
3 Correct 376 ms 45032 KB Output is correct
4 Correct 394 ms 45032 KB Output is correct
5 Correct 428 ms 45032 KB Output is correct
6 Correct 508 ms 45032 KB Output is correct
7 Correct 461 ms 45032 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 45032 KB Output is correct
2 Correct 325 ms 45032 KB Output is correct
3 Correct 285 ms 45032 KB Output is correct
4 Correct 276 ms 45032 KB Output is correct
5 Correct 300 ms 45032 KB Output is correct
6 Correct 318 ms 45032 KB Output is correct
7 Correct 265 ms 45032 KB Output is correct
8 Incorrect 287 ms 45032 KB Output isn't correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 10 ms 9960 KB Output is correct
3 Correct 12 ms 9960 KB Output is correct
4 Correct 12 ms 10188 KB Output is correct
5 Correct 430 ms 40472 KB Output is correct
6 Correct 428 ms 45032 KB Output is correct
7 Correct 376 ms 45032 KB Output is correct
8 Correct 394 ms 45032 KB Output is correct
9 Correct 428 ms 45032 KB Output is correct
10 Correct 508 ms 45032 KB Output is correct
11 Correct 461 ms 45032 KB Output is correct
12 Correct 317 ms 45032 KB Output is correct
13 Correct 325 ms 45032 KB Output is correct
14 Correct 285 ms 45032 KB Output is correct
15 Correct 276 ms 45032 KB Output is correct
16 Correct 300 ms 45032 KB Output is correct
17 Correct 318 ms 45032 KB Output is correct
18 Correct 265 ms 45032 KB Output is correct
19 Incorrect 287 ms 45032 KB Output isn't correct