oj.uz

Submission #242293

# Submission time Handle Problem Language Result Execution time Memory
242293 2020-06-27T08:22:37 Z jamielim Magic Tree (CEOI19_magictree) C++14
37 / 100
 130 ms 35064 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> ii;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
const int INF=2012345678;
const ll LLINF=4012345678012345678LL;
const ll MOD=1000000007; //998244353; //
const ld PI=3.1415926535898;
const ld EPS=1e-9;
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(b==0)return a;return gcd(b,a%b);}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll expo(ll b,ll p,ll m){ll res=1; while(p){if(p&1)res=(res*b)%m; b=(b*b)%m; p>>=1;} return res;}
inline ll modinv(ll a,ll m){return expo(a,m-2,m);}

int n,m,k;
vector<int> adj[100005];
ii r[100005];
ll memo[100005][25];

void dfs(int x){
	for(int i=0;i<SZ(adj[x]);i++){
		dfs(adj[x][i]);
		for(int j=0;j<25;j++){
			memo[x][j]+=memo[adj[x][i]][j];
		}
	}
	memo[x][r[x].fi]+=r[x].se;
	for(int i=1;i<25;i++){
		memo[x][i]=max(memo[x][i-1],memo[x][i]);
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	int p,v,d,w;
	for(int i=1;i<n;i++){
		scanf("%d",&p);p--;
		adj[p].pb(i);
	}
	for(int i=0;i<n;i++)r[i]=mp(0LL,0LL);
	bool st2=1;
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&v,&d,&w);v--;
		r[v]=mp(d,w);
		if(SZ(adj[v])!=0)st2=0;
	}
	if(st2){
		ll ans=0;
		for(int i=0;i<n;i++)ans+=r[i].se;
		printf("%lld",ans);
	}else{
		dfs(0);
		printf("%lld",memo[0][k]);
	}
}

Compilation message

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

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5632 KB Output is correct
2 Correct 38 ms 6784 KB Output is correct
3 Correct 63 ms 4984 KB Output is correct
4 Correct 60 ms 4728 KB Output is correct
5 Correct 61 ms 5112 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 25544 KB Output is correct
2 Correct 117 ms 25720 KB Output is correct
3 Correct 101 ms 29816 KB Output is correct
4 Correct 77 ms 24304 KB Output is correct
5 Correct 85 ms 35064 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 6 ms 2688 KB Output is correct
10 Correct 105 ms 25464 KB Output is correct
11 Correct 103 ms 25464 KB Output is correct
12 Correct 88 ms 29432 KB Output is correct
13 Correct 72 ms 24304 KB Output is correct
14 Correct 74 ms 34680 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 6 ms 2688 KB Output is correct
10 Incorrect 6 ms 3072 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 6 ms 2688 KB Output is correct
9 Correct 6 ms 2688 KB Output is correct
10 Correct 45 ms 5632 KB Output is correct
11 Correct 38 ms 6784 KB Output is correct
12 Correct 63 ms 4984 KB Output is correct
13 Correct 60 ms 4728 KB Output is correct
14 Correct 61 ms 5112 KB Output is correct
15 Incorrect 6 ms 3072 KB Output isn't correct
16 Halted 0 ms 0 KB -