oj.uz

Submission #867915

# Submission time Handle Problem Language Result Execution time Memory
867915 2023-10-29T19:01:32 Z parsadox2 Magic Tree (CEOI19_magictree) C++14
3 / 100
 98 ms 15956 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n , m , k , tree[N << 2] , st_tim[N] , fn_tim[N] , tim , dis[N];
vector <int> adj[N];
set <int> st;

struct fruit{
	int v , d , w;
};
vector <fruit> all;

bool cmp(fruit a , fruit b)
{
	if(a.d != b.d)
		return a.d > b.d;
	else
		return dis[a.v] < dis[b.v];
}

void Dfs(int v)
{
	st_tim[v] = tim++;
	for(auto u : adj[v])
	{
		dis[u] = dis[v] + 1;
		Dfs(u);
	}
	fn_tim[v] = tim;
}

int Get(int l , int r , int node = 1 , int nl = 0 , int nr = n)
{
	if(r <= nl || nr <= l)
		return 0;
	if(l <= nl && nr <= r)
		return tree[node];
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	return Get(l , r , lc , nl , mid) + Get(l , r , rc , mid , nr);
}

void Add(int ind , int val , int node = 1 , int nl = 0 , int nr = n)
{
	tree[node] += val;
	if(nr - nl == 1)
		return;
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	if(ind < mid)
		Add(ind , val , lc , nl , mid);
	else
		Add(ind , val , rc , mid , nr);
}

void Res(int ind , int node = 1 , int nl = 0 , int nr = n)
{
	if(nr - nl == 1)
	{
		tree[node] = 0;
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	if(ind < mid)
		Res(ind , lc , nl , mid);
	else
		Res(ind , rc , mid , nr);
	tree[node] = tree[lc] + tree[rc];
}

void ins(fruit a)
{
	st.insert(st_tim[a.v]);
	Add(st_tim[a.v] , a.w);
	auto it = st.upper_bound(st_tim[a.v]);
	if(it == st.end())
		return;
	int now = *it;
	vector <int> rem;
	while(now < fn_tim[a.v])
	{
		rem.push_back(now);
		Res(now);
		it++;
		if(it == st.end())
			break;
		now = *it;
	}
	for(auto u : rem)
		st.erase(u);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 2 ; i <= n ; i++)
	{
		int x;  cin >> x;
		adj[x].push_back(i);
	}
	for(int i = 0 ; i < m ; i++)
	{
		int v , d , w;  cin >> v >> d >> w;
		all.push_back({v , d , w});
	}
	Dfs(1);
	sort(all.begin() , all.end() , cmp);
	int ans = 0;
	for(auto u : all)
	{
		int val = Get(st_tim[u.v] , fn_tim[u.v]);
		if(u.w > val)
		{
			ans += u.w - val;
			ins(u);
		}
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10508 KB Output is correct
2 Correct 27 ms 12600 KB Output is correct
3 Correct 98 ms 15528 KB Output is correct
4 Correct 82 ms 14304 KB Output is correct
5 Correct 89 ms 15956 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5468 KB Output is correct
2 Correct 15 ms 9052 KB Output is correct
3 Correct 14 ms 8964 KB Output is correct
4 Correct 16 ms 9052 KB Output is correct
5 Correct 6 ms 7892 KB Output is correct
6 Incorrect 14 ms 9564 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -