oj.uz

Submission #227307

# Submission time Handle Problem Language Result Execution time Memory
227307 2020-04-26T17:49:26 Z ryansee Magic Tree (CEOI19_magictree) C++14
58 / 100
 2000 ms 26488 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 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;
	unite(t,t,R);
	unite(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;
	unite(t,t,R);
	unite(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);
}
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]));
			else if(myval+pre[co]>rmq(treap[old[x]],*j,*j)){
				update(treap[old[x]],*j,*j,-rmq(treap[old[x]],*j,*j)), 
				update(treap[old[x]],*j,*j,myval+pre[co]);
			}
			if(b4<rmq(treap[old[x]],*j,*j))
				update(treap[old[x]],(*j)+1, INF, rmq(treap[old[x]],*j,*j)-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(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,-rmq(treap[old[x]],A[x].f,A[x].f)),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';
	}
}
int main(){
	FAST
	cin>>n>>m>>k;
	FOR(i,2,n){
		ll p;cin>>p;
		v[p].eb(i), v[i].eb(p);
	}
	FOR(i,1,m){
		ll a;cin>>a;
		cin>>A[a].f>>A[a].s;
	}
	dfs(1,1);
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1598 ms 16704 KB Output is correct
2 Correct 788 ms 15856 KB Output is correct
3 Execution timed out 2087 ms 19920 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2944 KB Output is correct
2 Correct 8 ms 2944 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 328 ms 26232 KB Output is correct
5 Correct 272 ms 26360 KB Output is correct
6 Correct 1781 ms 26488 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 12528 KB Output is correct
2 Correct 110 ms 11628 KB Output is correct
3 Correct 125 ms 15148 KB Output is correct
4 Correct 150 ms 14952 KB Output is correct
5 Correct 92 ms 22264 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 6 ms 2688 KB Output is correct
10 Correct 713 ms 16752 KB Output is correct
11 Correct 467 ms 15216 KB Output is correct
12 Correct 304 ms 15356 KB Output is correct
13 Correct 698 ms 14956 KB Output is correct
14 Correct 220 ms 22264 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4096 KB Output is correct
2 Correct 59 ms 8692 KB Output is correct
3 Correct 60 ms 8692 KB Output is correct
4 Correct 65 ms 8820 KB Output is correct
5 Correct 34 ms 9488 KB Output is correct
6 Correct 56 ms 11672 KB Output is correct
7 Correct 51 ms 14072 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 6 ms 2688 KB Output is correct
10 Correct 7 ms 2944 KB Output is correct
11 Correct 8 ms 2944 KB Output is correct
12 Correct 6 ms 2944 KB Output is correct
13 Correct 328 ms 26232 KB Output is correct
14 Correct 272 ms 26360 KB Output is correct
15 Correct 1781 ms 26488 KB Output is correct
16 Correct 713 ms 16752 KB Output is correct
17 Correct 467 ms 15216 KB Output is correct
18 Correct 304 ms 15356 KB Output is correct
19 Correct 698 ms 14956 KB Output is correct
20 Correct 220 ms 22264 KB Output is correct
21 Correct 734 ms 7464 KB Output is correct
22 Execution timed out 2087 ms 18488 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 6 ms 2688 KB Output is correct
10 Correct 1598 ms 16704 KB Output is correct
11 Correct 788 ms 15856 KB Output is correct
12 Execution timed out 2087 ms 19920 KB Time limit exceeded
13 Halted 0 ms 0 KB -