oj.uz

답안 #73095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73095 2018-08-27T16:05:39 Z khohko Min-max tree (BOI18_minmaxtree) C++17
7 / 100
 1000 ms 263168 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 11 ms 9956 KB Output is correct
3 Correct 9 ms 9984 KB Output is correct
4 Correct 13 ms 9984 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 521 ms 69704 KB Output is correct
2 Correct 624 ms 99192 KB Output is correct
3 Execution timed out 1055 ms 263168 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 294 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 11 ms 9956 KB Output is correct
3 Correct 9 ms 9984 KB Output is correct
4 Correct 13 ms 9984 KB Output is correct
5 Correct 521 ms 69704 KB Output is correct
6 Correct 624 ms 99192 KB Output is correct
7 Execution timed out 1055 ms 263168 KB Time limit exceeded
8 Halted 0 ms 0 KB -