oj.uz

Submission #227305

# Submission time Handle Problem Language Result Execution time Memory
227305 2020-04-26T17:43:10 Z ryansee Magic Tree (CEOI19_magictree) C++14
33 / 100
 2000 ms 34068 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;
	int 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());
	}
	// 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;
	}
	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 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 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 8 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 Incorrect 1226 ms 27116 KB Output isn't correct
2 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 12 ms 7680 KB Output is correct
3 Correct 10 ms 7680 KB Output is correct
4 Correct 362 ms 33912 KB Output is correct
5 Correct 305 ms 33912 KB Output is correct
6 Correct 1897 ms 34068 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 20212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 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 8 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 754 ms 27376 KB Output is correct
11 Correct 487 ms 24944 KB Output is correct
12 Correct 417 ms 20864 KB Output is correct
13 Correct 611 ms 24044 KB Output is correct
14 Correct 247 ms 27000 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 8960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 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 8 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 12 ms 7680 KB Output is correct
12 Correct 10 ms 7680 KB Output is correct
13 Correct 362 ms 33912 KB Output is correct
14 Correct 305 ms 33912 KB Output is correct
15 Correct 1897 ms 34068 KB Output is correct
16 Correct 754 ms 27376 KB Output is correct
17 Correct 487 ms 24944 KB Output is correct
18 Correct 417 ms 20864 KB Output is correct
19 Correct 611 ms 24044 KB Output is correct
20 Correct 247 ms 27000 KB Output is correct
21 Correct 803 ms 14832 KB Output is correct
22 Execution timed out 2078 ms 29928 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 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 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 8 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Incorrect 1226 ms 27116 KB Output isn't correct
11 Halted 0 ms 0 KB -