oj.uz

답안 #73096

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73096 2018-08-27T16:06:30 Z khohko Min-max tree (BOI18_minmaxtree) C++17
29 / 100
 469 ms 41788 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 f[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;
}


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(mv(mp[mn[x]])){
			pas[x]=mn[x];
			mp[mn[x]]=x;
			return 1;
		}
	}
	f[x]=2;
	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++)
		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:91:5: warning: unused variable 'te' [-Wunused-variable]
  ll te=q;
     ^~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 9 ms 9832 KB Output is correct
3 Correct 9 ms 9832 KB Output is correct
4 Correct 15 ms 9904 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 375 ms 37396 KB Output is correct
2 Correct 385 ms 41788 KB Output is correct
3 Correct 397 ms 41788 KB Output is correct
4 Correct 446 ms 41788 KB Output is correct
5 Correct 469 ms 41788 KB Output is correct
6 Correct 416 ms 41788 KB Output is correct
7 Correct 413 ms 41788 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 41788 KB Output is correct
2 Correct 303 ms 41788 KB Output is correct
3 Correct 337 ms 41788 KB Output is correct
4 Correct 290 ms 41788 KB Output is correct
5 Correct 254 ms 41788 KB Output is correct
6 Correct 305 ms 41788 KB Output is correct
7 Correct 332 ms 41788 KB Output is correct
8 Incorrect 354 ms 41788 KB Output isn't correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 9 ms 9832 KB Output is correct
3 Correct 9 ms 9832 KB Output is correct
4 Correct 15 ms 9904 KB Output is correct
5 Correct 375 ms 37396 KB Output is correct
6 Correct 385 ms 41788 KB Output is correct
7 Correct 397 ms 41788 KB Output is correct
8 Correct 446 ms 41788 KB Output is correct
9 Correct 469 ms 41788 KB Output is correct
10 Correct 416 ms 41788 KB Output is correct
11 Correct 413 ms 41788 KB Output is correct
12 Correct 320 ms 41788 KB Output is correct
13 Correct 303 ms 41788 KB Output is correct
14 Correct 337 ms 41788 KB Output is correct
15 Correct 290 ms 41788 KB Output is correct
16 Correct 254 ms 41788 KB Output is correct
17 Correct 305 ms 41788 KB Output is correct
18 Correct 332 ms 41788 KB Output is correct
19 Incorrect 354 ms 41788 KB Output isn't correct