oj.uz

Submission #896248

# Submission time Handle Problem Language Result Execution time Memory
896248 2024-01-01T05:18:40 Z 8pete8 Magic Tree (CEOI19_magictree) C++17
100 / 100
 117 ms 101640 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<float.h>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
#define double long double
const int mod=998244353,mxn=1e6,lg=22;//inf=1e18,minf=-1e18,Mxn=100000;
vector<int>adj[mxn+10];
map<int,int>mp[mxn+10];
pii info[mxn+10];
int n,m,k;
ll ans=0;
void dfs2(int cur,int p){
	for(auto i:adj[cur]){
		dfs2(i,cur);
		if(mp[i].size()>mp[cur].size())swap(mp[cur],mp[i]);
		for(auto j:mp[i])mp[cur][j.f]+=j.s;
	}
	mp[cur][info[cur].f]+=info[cur].s;
	auto it=mp[cur].upper_bound(info[cur].f);
	while(it!=mp[cur].end()&&info[cur].s){
		if(it==mp[cur].end())assert(0);
		if(info[cur].s>=it->s)info[cur].s-=it->s,it=mp[cur].erase(it);
		else it->s-=info[cur].s,info[cur].s=0;
	}
}
int32_t main(){
    fastio
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		int p;cin>>p;
		adj[p].pb(i);
	}
	bool yes=true;
	for(int i=0;i<m;i++){
		int v,d,w;cin>>v>>d>>w;
		info[v]={d,w};
	}
	ans=0;
	dfs2(1,-1);
	for(auto i:mp[1])ans+=i.s;
	cout<<ans;
	return 0;
}

Compilation message

magictree.cpp: In function 'int32_t main()':
magictree.cpp:64:7: warning: unused variable 'yes' [-Wunused-variable]
   64 |  bool yes=true;
      |       ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 71772 KB Output is correct
2 Correct 14 ms 72028 KB Output is correct
3 Correct 15 ms 71772 KB Output is correct
4 Correct 15 ms 71928 KB Output is correct
5 Correct 15 ms 71772 KB Output is correct
6 Correct 15 ms 71964 KB Output is correct
7 Correct 15 ms 71952 KB Output is correct
8 Correct 15 ms 72028 KB Output is correct
9 Correct 15 ms 71768 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 86308 KB Output is correct
2 Correct 49 ms 85084 KB Output is correct
3 Correct 117 ms 101640 KB Output is correct
4 Correct 68 ms 84944 KB Output is correct
5 Correct 94 ms 86096 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 72024 KB Output is correct
2 Correct 15 ms 72028 KB Output is correct
3 Correct 17 ms 72024 KB Output is correct
4 Correct 51 ms 91220 KB Output is correct
5 Correct 70 ms 95208 KB Output is correct
6 Correct 62 ms 91480 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 80468 KB Output is correct
2 Correct 59 ms 79428 KB Output is correct
3 Correct 50 ms 83540 KB Output is correct
4 Correct 42 ms 81112 KB Output is correct
5 Correct 49 ms 91220 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 71772 KB Output is correct
2 Correct 14 ms 72028 KB Output is correct
3 Correct 15 ms 71772 KB Output is correct
4 Correct 15 ms 71928 KB Output is correct
5 Correct 15 ms 71772 KB Output is correct
6 Correct 15 ms 71964 KB Output is correct
7 Correct 15 ms 71952 KB Output is correct
8 Correct 15 ms 72028 KB Output is correct
9 Correct 15 ms 71768 KB Output is correct
10 Correct 65 ms 83340 KB Output is correct
11 Correct 61 ms 82260 KB Output is correct
12 Correct 50 ms 83492 KB Output is correct
13 Correct 41 ms 81100 KB Output is correct
14 Correct 53 ms 91216 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 75284 KB Output is correct
2 Correct 44 ms 79896 KB Output is correct
3 Correct 43 ms 79728 KB Output is correct
4 Correct 42 ms 79924 KB Output is correct
5 Correct 28 ms 81360 KB Output is correct
6 Correct 40 ms 83028 KB Output is correct
7 Correct 37 ms 84048 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 71772 KB Output is correct
2 Correct 14 ms 72028 KB Output is correct
3 Correct 15 ms 71772 KB Output is correct
4 Correct 15 ms 71928 KB Output is correct
5 Correct 15 ms 71772 KB Output is correct
6 Correct 15 ms 71964 KB Output is correct
7 Correct 15 ms 71952 KB Output is correct
8 Correct 15 ms 72028 KB Output is correct
9 Correct 15 ms 71768 KB Output is correct
10 Correct 15 ms 72024 KB Output is correct
11 Correct 15 ms 72028 KB Output is correct
12 Correct 17 ms 72024 KB Output is correct
13 Correct 51 ms 91220 KB Output is correct
14 Correct 70 ms 95208 KB Output is correct
15 Correct 62 ms 91480 KB Output is correct
16 Correct 65 ms 83340 KB Output is correct
17 Correct 61 ms 82260 KB Output is correct
18 Correct 50 ms 83492 KB Output is correct
19 Correct 41 ms 81100 KB Output is correct
20 Correct 53 ms 91216 KB Output is correct
21 Correct 29 ms 77592 KB Output is correct
22 Correct 74 ms 86224 KB Output is correct
23 Correct 79 ms 89424 KB Output is correct
24 Correct 113 ms 95824 KB Output is correct
25 Correct 65 ms 84944 KB Output is correct
26 Correct 87 ms 86356 KB Output is correct
27 Correct 70 ms 85072 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 71772 KB Output is correct
2 Correct 14 ms 72028 KB Output is correct
3 Correct 15 ms 71772 KB Output is correct
4 Correct 15 ms 71928 KB Output is correct
5 Correct 15 ms 71772 KB Output is correct
6 Correct 15 ms 71964 KB Output is correct
7 Correct 15 ms 71952 KB Output is correct
8 Correct 15 ms 72028 KB Output is correct
9 Correct 15 ms 71768 KB Output is correct
10 Correct 64 ms 86308 KB Output is correct
11 Correct 49 ms 85084 KB Output is correct
12 Correct 117 ms 101640 KB Output is correct
13 Correct 68 ms 84944 KB Output is correct
14 Correct 94 ms 86096 KB Output is correct
15 Correct 15 ms 72024 KB Output is correct
16 Correct 15 ms 72028 KB Output is correct
17 Correct 17 ms 72024 KB Output is correct
18 Correct 51 ms 91220 KB Output is correct
19 Correct 70 ms 95208 KB Output is correct
20 Correct 62 ms 91480 KB Output is correct
21 Correct 57 ms 80468 KB Output is correct
22 Correct 59 ms 79428 KB Output is correct
23 Correct 50 ms 83540 KB Output is correct
24 Correct 42 ms 81112 KB Output is correct
25 Correct 49 ms 91220 KB Output is correct
26 Correct 65 ms 83340 KB Output is correct
27 Correct 61 ms 82260 KB Output is correct
28 Correct 50 ms 83492 KB Output is correct
29 Correct 41 ms 81100 KB Output is correct
30 Correct 53 ms 91216 KB Output is correct
31 Correct 20 ms 75284 KB Output is correct
32 Correct 44 ms 79896 KB Output is correct
33 Correct 43 ms 79728 KB Output is correct
34 Correct 42 ms 79924 KB Output is correct
35 Correct 28 ms 81360 KB Output is correct
36 Correct 40 ms 83028 KB Output is correct
37 Correct 37 ms 84048 KB Output is correct
38 Correct 29 ms 77592 KB Output is correct
39 Correct 74 ms 86224 KB Output is correct
40 Correct 79 ms 89424 KB Output is correct
41 Correct 113 ms 95824 KB Output is correct
42 Correct 65 ms 84944 KB Output is correct
43 Correct 87 ms 86356 KB Output is correct
44 Correct 70 ms 85072 KB Output is correct
45 Correct 32 ms 77908 KB Output is correct
46 Correct 85 ms 88560 KB Output is correct
47 Correct 85 ms 91952 KB Output is correct
48 Correct 115 ms 100432 KB Output is correct
49 Correct 75 ms 86948 KB Output is correct
50 Correct 89 ms 88984 KB Output is correct
51 Correct 78 ms 87884 KB Output is correct