oj.uz

Submission #277699

# Submission time Handle Problem Language Result Execution time Memory
277699 2020-08-21T06:53:10 Z Fasho Magic Tree (CEOI19_magictree) C++14
34 / 100
 161 ms 33784 KB 
#include <bits/stdc++.h>
#define N 100005
#define ll long long int
#define fo(i,x,y)	for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define mod 1000000007
using namespace std;

ll n,m,ar[N],sum,t,k,dp[N][21],val[N];

vector<int> v[N];

ll f(int ind,int back,int l)
{
	if(dp[ind][l]!=-1)
		return dp[ind][l];
	ll t1=0;
	ll t2=0;
	for(int i=0;i<v[ind].size();i++)
		t1+=f(v[ind][i],ind,l);
	if(ar[ind]<l && ar[ind]!=0)
		for(int i=0;i<v[ind].size();i++)
			t2+=f(v[ind][i],ind,ar[ind]);

	if(ar[ind]<l && ar[ind]!=0)
		t2+=val[ind];
	if(ar[ind]==l && l!=0)
		t1+=val[ind];
	// cout<<ind<<sp<<l<<sp<<t1<<sp<<t2<<endl;
	return dp[ind][l]=max(t1,t2);
}

int main()
{
	fast;
	cin>>n>>m>>k;
	memset(dp,-1,sizeof(dp));
	fo(i,2,n)
	{
		int a;
		cin>>a;
		v[a].pb(i);
	}
	fo(i,1,m)
	{
		ll a,b,c;
		cin>>a>>b>>c;
		ar[a]=b;
		val[a]=c;
	}
	// fo(i,1,n)
	// cout<<ar[i]<<sp;
	// cout<<endl;

	// fo(i,1,n)
	// cout<<val[i]<<sp;
	// cout<<endl;

	cout<<f(1,1,20);

}

Compilation message

magictree.cpp: In function 'long long int f(int, int, int)':
magictree.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~
magictree.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i=0;i<v[ind].size();i++)
      |               ~^~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19072 KB Output is correct
2 Correct 14 ms 19200 KB Output is correct
3 Correct 12 ms 19072 KB Output is correct
4 Correct 12 ms 19072 KB Output is correct
5 Correct 12 ms 19072 KB Output is correct
6 Correct 13 ms 19072 KB Output is correct
7 Correct 12 ms 19072 KB Output is correct
8 Correct 15 ms 19072 KB Output is correct
9 Correct 12 ms 19072 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 24440 KB Output is correct
2 Correct 92 ms 24440 KB Output is correct
3 Correct 85 ms 28408 KB Output is correct
4 Correct 56 ms 23024 KB Output is correct
5 Correct 67 ms 33784 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19072 KB Output is correct
2 Correct 14 ms 19200 KB Output is correct
3 Correct 12 ms 19072 KB Output is correct
4 Correct 12 ms 19072 KB Output is correct
5 Correct 12 ms 19072 KB Output is correct
6 Correct 13 ms 19072 KB Output is correct
7 Correct 12 ms 19072 KB Output is correct
8 Correct 15 ms 19072 KB Output is correct
9 Correct 12 ms 19072 KB Output is correct
10 Correct 161 ms 23800 KB Output is correct
11 Correct 116 ms 23672 KB Output is correct
12 Correct 111 ms 27768 KB Output is correct
13 Correct 45 ms 22424 KB Output is correct
14 Correct 85 ms 33272 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19072 KB Output is correct
2 Correct 14 ms 19200 KB Output is correct
3 Correct 12 ms 19072 KB Output is correct
4 Correct 12 ms 19072 KB Output is correct
5 Correct 12 ms 19072 KB Output is correct
6 Correct 13 ms 19072 KB Output is correct
7 Correct 12 ms 19072 KB Output is correct
8 Correct 15 ms 19072 KB Output is correct
9 Correct 12 ms 19072 KB Output is correct
10 Correct 13 ms 19200 KB Output is correct
11 Incorrect 12 ms 19200 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19072 KB Output is correct
2 Correct 14 ms 19200 KB Output is correct
3 Correct 12 ms 19072 KB Output is correct
4 Correct 12 ms 19072 KB Output is correct
5 Correct 12 ms 19072 KB Output is correct
6 Correct 13 ms 19072 KB Output is correct
7 Correct 12 ms 19072 KB Output is correct
8 Correct 15 ms 19072 KB Output is correct
9 Correct 12 ms 19072 KB Output is correct
10 Incorrect 53 ms 23344 KB Output isn't correct
11 Halted 0 ms 0 KB -