oj.uz

Submission #251953

# Submission time Handle Problem Language Result Execution time Memory
251953 2020-07-23T09:10:04 Z ryansee Magic Tree (CEOI19_magictree) C++14
100 / 100
 1686 ms 37104 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
 
typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;
 
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (100006)
ll n, m, k, old[MAXN];
vector<int> v[MAXN];
pi A[MAXN];
struct node{
	ll prior;
	int sz, key;
	ll val, lazy, mx;
	node*l=0,*r=0;
};
typedef node* pnode;
vector<pnode> treap;
pnode init(ll _key,ll nval){
	pnode tmp=new node;
	tmp->prior=rng(), tmp->sz=1, tmp->key=_key, tmp->val=nval, tmp->lazy=0, tmp->mx=nval;
	tmp->l=0, tmp->r=0;
	return tmp;
}
void push(pnode t){
	if(!t)return;
	t->val += t->lazy, t->mx += t->lazy;
	if(t->l) t->l->lazy+=t->lazy;
	if(t->r) t->r->lazy+=t->lazy;
	t->lazy=0;
}
void pull(pnode t){
	if(!t)return;
	if(t->l) push(t->l);
	if(t->r) push(t->r);
	t->mx=max({(t->l?t->l->mx:0),(t->r?t->r->mx:0),t->val});
}
void upd(pnode t){
	if(!t) return;
	t->sz = (t->l?t->l->sz:0) + (t->r?t->r->sz:0) + 1;
}
void split(pnode t,pnode&l,pnode&r,ll nval){
	if(!t) return void(l=r=0);
	push(t);
	if(t->key <= nval) split(t->r, t->r, r, nval), l=t;
	else split(t->l,l,t->l,nval),r=t;
	upd(t), pull(t);
}
void merge(pnode&t, pnode l,pnode r){
	if(!l || !r) return void(t=l?l:r);
	push(l),push(r);
	if(l->prior<r->prior) merge(r->l,l,r->l), t=r;
	else merge(l->r,l->r,r),t=l;
	upd(t), pull(t);
}
void unite(pnode&t,pnode l,pnode r){
	if(!l || !r) return void(t=l?l:r);
	push(l),push(r);
	if(l->prior < r->prior) swap(l,r);
	pnode L,R;
	split(r,L,R,l->key);
	unite(l->l,l->l,L);
	unite(l->r,l->r,R);
	t=l;
	upd(t);
	pull(t);
}
bool find(pnode t,ll key){
	if(!t) return 0;
	if(t->key==key) return 1;
	else if(t->key>key) return find(t->l,key);
	else return find(t->r,key);
}
void update(pnode t,ll l,ll r,ll nval){
	pnode L,R;
	split(t,L,t,l-1);
	split(t,t,R,r);
	if(t) t->lazy += nval;
	merge(t,t,R);
	merge(t,L,t);
}
ll rmq(pnode t,ll l,ll r){
	pnode L,R;
	split(t,L,t,l-1);
	split(t,t,R,r);
	ll ans=t ? t->mx+t->lazy : 0;
	merge(t,t,R);
	merge(t,L,t);
	return ans;
}
vector<int> s;
void it(pnode t){
	if(!t) return;
	it(t->l);
	s.pb(t->key);
	it(t->r);
}
ll memo;
void dfs(int x,int p){
	old[x]=-1;
	for(auto i:v[x]) if(i^p) {
		dfs(i, x);
		if(old[x]==-1 || (treap[old[i]]?treap[old[i]]->sz:0)>(treap[old[x]]?treap[old[x]]->sz:0)) old[x]=old[i];
	}
	if(old[x]==-1){
		old[x]=treap.size();
		treap.eb(pnode());
	}
	// i is updated by j, where j is largest < i
	for(auto i:v[x]) if((i^p) && (old[i]^old[x])) {
		s.clear();
		it(treap[old[i]]);
		vector<ll> pre;
		for(auto j=s.begin();j!=s.end();++j){
			pre.eb(rmq(treap[old[x]],0,*j));
		}
		ll co=0;
		for(auto j=s.begin();j!=s.end();++j){
			ll myval=rmq(treap[old[i]],*j,*j);
			ll b4=rmq(treap[old[x]],0,*j);
			if(!find(treap[old[x]],*j))unite(treap[old[x]],treap[old[x]],init(*j,myval+pre[co])),memo=myval+pre[co];
			else if(myval+pre[co]>(memo=rmq(treap[old[x]],*j,*j))){
				update(treap[old[x]],*j,*j,-memo), 
				update(treap[old[x]],*j,*j,myval+pre[co]);
				memo=myval+pre[co];
			}
			if(b4<memo)
				update(treap[old[x]],(*j)+1, INF, memo-b4);
			++ co;
		}
	}
	if(A[x].f){
		ll pre=rmq(treap[old[x]],0,A[x].f);
		if(!find(treap[old[x]],A[x].f))unite(treap[old[x]],treap[old[x]],init(A[x].f,A[x].s+pre));
		else if((memo=rmq(treap[old[x]],A[x].f,A[x].f))==pre) update(treap[old[x]],A[x].f,A[x].f,A[x].s);
		else update(treap[old[x]],A[x].f,A[x].f,-memo),update(treap[old[x]],A[x].f,A[x].f,pre+A[x].s);
	}
	if(x==1){
		cout<<rmq(treap[old[x]],0,INF)<<'\n';
	}
}
#define gc getchar_unlocked
void in(ll&x){
	x=0;
	char ch=gc();
	while(ch<'0'||ch>'9')ch=gc();
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch&15);
		ch=gc();
	}
}
int main(){
	FAST
	in(n),in(m),in(k);
	FOR(i,2,n){
		ll p;in(p);
		v[p].eb(i), v[i].eb(p);
	}
	FOR(i,1,m){
		ll a;in(a);
		in(A[a].f),in(A[a].s);
	}
	dfs(1,1);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 17648 KB Output is correct
2 Correct 193 ms 16884 KB Output is correct
3 Correct 1686 ms 36748 KB Output is correct
4 Correct 716 ms 20844 KB Output is correct
5 Correct 749 ms 22508 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2944 KB Output is correct
2 Correct 4 ms 2944 KB Output is correct
3 Correct 2 ms 2944 KB Output is correct
4 Correct 193 ms 28152 KB Output is correct
5 Correct 159 ms 28152 KB Output is correct
6 Correct 535 ms 28280 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 14836 KB Output is correct
2 Correct 73 ms 13680 KB Output is correct
3 Correct 68 ms 17272 KB Output is correct
4 Correct 73 ms 16708 KB Output is correct
5 Correct 50 ms 24568 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 348 ms 18032 KB Output is correct
11 Correct 237 ms 16632 KB Output is correct
12 Correct 135 ms 16632 KB Output is correct
13 Correct 180 ms 16164 KB Output is correct
14 Correct 118 ms 23804 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4224 KB Output is correct
2 Correct 38 ms 9340 KB Output is correct
3 Correct 52 ms 9336 KB Output is correct
4 Correct 42 ms 9332 KB Output is correct
5 Correct 16 ms 9616 KB Output is correct
6 Correct 37 ms 12320 KB Output is correct
7 Correct 33 ms 14848 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 3 ms 2944 KB Output is correct
11 Correct 4 ms 2944 KB Output is correct
12 Correct 2 ms 2944 KB Output is correct
13 Correct 193 ms 28152 KB Output is correct
14 Correct 159 ms 28152 KB Output is correct
15 Correct 535 ms 28280 KB Output is correct
16 Correct 348 ms 18032 KB Output is correct
17 Correct 237 ms 16632 KB Output is correct
18 Correct 135 ms 16632 KB Output is correct
19 Correct 180 ms 16164 KB Output is correct
20 Correct 118 ms 23804 KB Output is correct
21 Correct 235 ms 7672 KB Output is correct
22 Correct 666 ms 19364 KB Output is correct
23 Correct 817 ms 23728 KB Output is correct
24 Correct 1617 ms 36484 KB Output is correct
25 Correct 686 ms 20332 KB Output is correct
26 Correct 793 ms 23280 KB Output is correct
27 Correct 712 ms 23408 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 429 ms 17648 KB Output is correct
11 Correct 193 ms 16884 KB Output is correct
12 Correct 1686 ms 36748 KB Output is correct
13 Correct 716 ms 20844 KB Output is correct
14 Correct 749 ms 22508 KB Output is correct
15 Correct 3 ms 2944 KB Output is correct
16 Correct 4 ms 2944 KB Output is correct
17 Correct 2 ms 2944 KB Output is correct
18 Correct 193 ms 28152 KB Output is correct
19 Correct 159 ms 28152 KB Output is correct
20 Correct 535 ms 28280 KB Output is correct
21 Correct 100 ms 14836 KB Output is correct
22 Correct 73 ms 13680 KB Output is correct
23 Correct 68 ms 17272 KB Output is correct
24 Correct 73 ms 16708 KB Output is correct
25 Correct 50 ms 24568 KB Output is correct
26 Correct 348 ms 18032 KB Output is correct
27 Correct 237 ms 16632 KB Output is correct
28 Correct 135 ms 16632 KB Output is correct
29 Correct 180 ms 16164 KB Output is correct
30 Correct 118 ms 23804 KB Output is correct
31 Correct 12 ms 4224 KB Output is correct
32 Correct 38 ms 9340 KB Output is correct
33 Correct 52 ms 9336 KB Output is correct
34 Correct 42 ms 9332 KB Output is correct
35 Correct 16 ms 9616 KB Output is correct
36 Correct 37 ms 12320 KB Output is correct
37 Correct 33 ms 14848 KB Output is correct
38 Correct 235 ms 7672 KB Output is correct
39 Correct 666 ms 19364 KB Output is correct
40 Correct 817 ms 23728 KB Output is correct
41 Correct 1617 ms 36484 KB Output is correct
42 Correct 686 ms 20332 KB Output is correct
43 Correct 793 ms 23280 KB Output is correct
44 Correct 712 ms 23408 KB Output is correct
45 Correct 228 ms 7800 KB Output is correct
46 Correct 645 ms 19824 KB Output is correct
47 Correct 803 ms 23872 KB Output is correct
48 Correct 1663 ms 37104 KB Output is correct
49 Correct 689 ms 21100 KB Output is correct
50 Correct 865 ms 24048 KB Output is correct
51 Correct 681 ms 24088 KB Output is correct