oj.uz

Submission #227304

# Submission time Handle Problem Language Result Execution time Memory
227304 2020-04-26T17:41:07 Z ryansee Magic Tree (CEOI19_magictree) C++14
58 / 100
 2000 ms 35756 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];
set<int> s[MAXN];
struct node{
	ll prior, sz, key, 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;
}
void dfs(int x,int p){
	old[x]=-1;
	for(auto i:v[x]) if(i^p) {
		dfs(i, x);
		if(old[x]==-1 || s[old[i]].size()>s[old[x]].size()) old[x]=old[i];
	}
	if(old[x]==-1){
		old[x]=treap.size();
		treap.eb(pnode());
		assert(!treap.back());
	}
	// i is updated by j, where j is largest < i
	for(auto i:v[x]) if((i^p) && (old[i]^old[x])) {
		vector<ll> pre;
		for(auto j=s[old[i]].begin();j!=s[old[i]].end();++j){
			pre.eb(rmq(treap[old[x]],0,*j));
		}
		ll co=0;
		for(auto j=s[old[i]].begin();j!=s[old[i]].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);
			s[old[x]].ins(*j);
			++ 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);
		s[old[x]].ins(A[x].f);
	}
	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;
		assert(A[a].f);
	}
	dfs(1,1);
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1613 ms 29272 KB Output is correct
2 Correct 823 ms 24564 KB Output is correct
3 Execution timed out 2054 ms 35756 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7680 KB Output is correct
2 Correct 11 ms 7680 KB Output is correct
3 Correct 9 ms 7680 KB Output is correct
4 Correct 371 ms 34984 KB Output is correct
5 Correct 310 ms 34936 KB Output is correct
6 Correct 1878 ms 34988 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 21100 KB Output is correct
2 Correct 128 ms 21284 KB Output is correct
3 Correct 122 ms 23088 KB Output is correct
4 Correct 159 ms 27116 KB Output is correct
5 Correct 98 ms 29048 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 10 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 740 ms 30552 KB Output is correct
11 Correct 498 ms 27884 KB Output is correct
12 Correct 380 ms 22388 KB Output is correct
13 Correct 612 ms 26600 KB Output is correct
14 Correct 264 ms 28408 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8960 KB Output is correct
2 Correct 63 ms 14168 KB Output is correct
3 Correct 65 ms 14068 KB Output is correct
4 Correct 69 ms 14320 KB Output is correct
5 Correct 39 ms 14372 KB Output is correct
6 Correct 61 ms 17076 KB Output is correct
7 Correct 54 ms 19448 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 10 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 9 ms 7680 KB Output is correct
11 Correct 11 ms 7680 KB Output is correct
12 Correct 9 ms 7680 KB Output is correct
13 Correct 371 ms 34984 KB Output is correct
14 Correct 310 ms 34936 KB Output is correct
15 Correct 1878 ms 34988 KB Output is correct
16 Correct 740 ms 30552 KB Output is correct
17 Correct 498 ms 27884 KB Output is correct
18 Correct 380 ms 22388 KB Output is correct
19 Correct 612 ms 26600 KB Output is correct
20 Correct 264 ms 28408 KB Output is correct
21 Correct 757 ms 15788 KB Output is correct
22 Execution timed out 2092 ms 33844 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 10 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 1613 ms 29272 KB Output is correct
11 Correct 823 ms 24564 KB Output is correct
12 Execution timed out 2054 ms 35756 KB Time limit exceeded
13 Halted 0 ms 0 KB -