oj.uz

Submission #579406

# Submission time Handle Problem Language Result Execution time Memory
579406 2022-06-19T05:27:31 Z temporary_juggernaut Magic Tree (CEOI19_magictree) C++14
100 / 100
 161 ms 36600 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
vector<int>g[100005];
int d[100005];
int w[100005];
int n,m,k;
map<int,ll>mp[100005];
int id[100005];
void dfs(int v){
	int mx=0;
	for(int to:g[v]){
		dfs(to);
		if(!mx||mp[id[to]].size()>mp[id[mx]].size())mx=to;
	}
	if(!mx){
		id[v]=v;
		if(w[v])mp[v][d[v]]+=w[v];
		return;
	}
	id[v]=id[mx];
	for(int to:g[v])if(to^mx)for(auto tmp:mp[id[to]])mp[id[v]][tmp.fr]+=tmp.second;
	mp[id[v]][d[v]]+=w[v];
	auto x=mp[id[v]].upper_bound(d[v]);
	x->sc-=w[v];
	while(x!=mp[id[v]].end()){
		auto y=x;
		y++;
		if(x->sc>=0)break;
		if(y!=mp[id[v]].end())y->second+=x->second;
		mp[id[v]].erase(x->first);
		x=y;
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=2;i<=n;i++){
		int x;
		scanf("%d",&x);
		g[x].push_back(i);
	}
	while(m--){
		int v;
		scanf("%d",&v);
		scanf("%d%d",&d[v],&w[v]);
	}
	ll ans=0;
	dfs(1);
	for(auto to:mp[id[1]])ans+=to.sc;
	cout<<ans;
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d%d%d",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
magictree.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~
magictree.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d",&v);
      |   ~~~~~^~~~~~~~~
magictree.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d%d",&d[v],&w[v]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 20020 KB Output is correct
2 Correct 55 ms 21224 KB Output is correct
3 Correct 161 ms 36268 KB Output is correct
4 Correct 95 ms 20332 KB Output is correct
5 Correct 124 ms 22604 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 5 ms 7488 KB Output is correct
4 Correct 66 ms 30448 KB Output is correct
5 Correct 80 ms 34732 KB Output is correct
6 Correct 88 ms 30832 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 15744 KB Output is correct
2 Correct 73 ms 14888 KB Output is correct
3 Correct 65 ms 20720 KB Output is correct
4 Correct 45 ms 16192 KB Output is correct
5 Correct 55 ms 30420 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7340 KB Output is correct
2 Correct 5 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 5 ms 7348 KB Output is correct
5 Correct 5 ms 7252 KB Output is correct
6 Correct 5 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7348 KB Output is correct
10 Correct 83 ms 19536 KB Output is correct
11 Correct 76 ms 18176 KB Output is correct
12 Correct 62 ms 20464 KB Output is correct
13 Correct 40 ms 15552 KB Output is correct
14 Correct 52 ms 30284 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8404 KB Output is correct
2 Correct 43 ms 12228 KB Output is correct
3 Correct 39 ms 12128 KB Output is correct
4 Correct 39 ms 12332 KB Output is correct
5 Correct 14 ms 9276 KB Output is correct
6 Correct 32 ms 13900 KB Output is correct
7 Correct 37 ms 18508 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7340 KB Output is correct
2 Correct 5 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 5 ms 7348 KB Output is correct
5 Correct 5 ms 7252 KB Output is correct
6 Correct 5 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7348 KB Output is correct
10 Correct 4 ms 7508 KB Output is correct
11 Correct 4 ms 7508 KB Output is correct
12 Correct 5 ms 7488 KB Output is correct
13 Correct 66 ms 30448 KB Output is correct
14 Correct 80 ms 34732 KB Output is correct
15 Correct 88 ms 30832 KB Output is correct
16 Correct 83 ms 19536 KB Output is correct
17 Correct 76 ms 18176 KB Output is correct
18 Correct 62 ms 20464 KB Output is correct
19 Correct 40 ms 15552 KB Output is correct
20 Correct 52 ms 30284 KB Output is correct
21 Correct 25 ms 11448 KB Output is correct
22 Correct 91 ms 21496 KB Output is correct
23 Correct 102 ms 25832 KB Output is correct
24 Correct 144 ms 36600 KB Output is correct
25 Correct 70 ms 19692 KB Output is correct
26 Correct 114 ms 23272 KB Output is correct
27 Correct 90 ms 23100 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7340 KB Output is correct
2 Correct 5 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 5 ms 7348 KB Output is correct
5 Correct 5 ms 7252 KB Output is correct
6 Correct 5 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7348 KB Output is correct
10 Correct 71 ms 20020 KB Output is correct
11 Correct 55 ms 21224 KB Output is correct
12 Correct 161 ms 36268 KB Output is correct
13 Correct 95 ms 20332 KB Output is correct
14 Correct 124 ms 22604 KB Output is correct
15 Correct 4 ms 7508 KB Output is correct
16 Correct 4 ms 7508 KB Output is correct
17 Correct 5 ms 7488 KB Output is correct
18 Correct 66 ms 30448 KB Output is correct
19 Correct 80 ms 34732 KB Output is correct
20 Correct 88 ms 30832 KB Output is correct
21 Correct 71 ms 15744 KB Output is correct
22 Correct 73 ms 14888 KB Output is correct
23 Correct 65 ms 20720 KB Output is correct
24 Correct 45 ms 16192 KB Output is correct
25 Correct 55 ms 30420 KB Output is correct
26 Correct 83 ms 19536 KB Output is correct
27 Correct 76 ms 18176 KB Output is correct
28 Correct 62 ms 20464 KB Output is correct
29 Correct 40 ms 15552 KB Output is correct
30 Correct 52 ms 30284 KB Output is correct
31 Correct 10 ms 8404 KB Output is correct
32 Correct 43 ms 12228 KB Output is correct
33 Correct 39 ms 12128 KB Output is correct
34 Correct 39 ms 12332 KB Output is correct
35 Correct 14 ms 9276 KB Output is correct
36 Correct 32 ms 13900 KB Output is correct
37 Correct 37 ms 18508 KB Output is correct
38 Correct 25 ms 11448 KB Output is correct
39 Correct 91 ms 21496 KB Output is correct
40 Correct 102 ms 25832 KB Output is correct
41 Correct 144 ms 36600 KB Output is correct
42 Correct 70 ms 19692 KB Output is correct
43 Correct 114 ms 23272 KB Output is correct
44 Correct 90 ms 23100 KB Output is correct
45 Correct 21 ms 11180 KB Output is correct
46 Correct 81 ms 21104 KB Output is correct
47 Correct 95 ms 24332 KB Output is correct
48 Correct 132 ms 33756 KB Output is correct
49 Correct 73 ms 20280 KB Output is correct
50 Correct 145 ms 23400 KB Output is correct
51 Correct 99 ms 23240 KB Output is correct