oj.uz

Submission #227306

# Submission time Handle Problem Language Result Execution time Memory
227306 2020-04-26T17:44:05 Z ryansee Magic Tree (CEOI19_magictree) C++14
58 / 100
 2000 ms 33912 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 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->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 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;
	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;
	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 8 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 8 ms 7424 KB Output is correct
6 Correct 8 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 9 ms 7424 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1596 ms 26992 KB Output is correct
2 Correct 853 ms 23088 KB Output is correct
3 Execution timed out 2086 ms 33060 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 365 ms 33912 KB Output is correct
5 Correct 344 ms 33912 KB Output is correct
6 Correct 1734 ms 33912 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 20080 KB Output is correct
2 Correct 124 ms 18544 KB Output is correct
3 Correct 112 ms 20724 KB Output is correct
4 Correct 169 ms 24056 KB Output is correct
5 Correct 101 ms 27256 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 7424 KB Output is correct
6 Correct 8 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 9 ms 7424 KB Output is correct
10 Correct 717 ms 26996 KB Output is correct
11 Correct 478 ms 24816 KB Output is correct
12 Correct 378 ms 20596 KB Output is correct
13 Correct 508 ms 23916 KB Output is correct
14 Correct 273 ms 27000 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 8960 KB Output is correct
2 Correct 62 ms 13676 KB Output is correct
3 Correct 62 ms 13556 KB Output is correct
4 Correct 65 ms 13808 KB Output is correct
5 Correct 38 ms 14228 KB Output is correct
6 Correct 58 ms 16560 KB Output is correct
7 Correct 58 ms 18936 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 7424 KB Output is correct
6 Correct 8 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 9 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 365 ms 33912 KB Output is correct
14 Correct 344 ms 33912 KB Output is correct
15 Correct 1734 ms 33912 KB Output is correct
16 Correct 717 ms 26996 KB Output is correct
17 Correct 478 ms 24816 KB Output is correct
18 Correct 378 ms 20596 KB Output is correct
19 Correct 508 ms 23916 KB Output is correct
20 Correct 273 ms 27000 KB Output is correct
21 Correct 753 ms 14556 KB Output is correct
22 Execution timed out 2088 ms 30192 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 7424 KB Output is correct
6 Correct 8 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 9 ms 7424 KB Output is correct
10 Correct 1596 ms 26992 KB Output is correct
11 Correct 853 ms 23088 KB Output is correct
12 Execution timed out 2086 ms 33060 KB Time limit exceeded
13 Halted 0 ms 0 KB -