답안 #128090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128090	2019-07-10T12:06:24 Z	faustaadp	Chase (CEOI17_chase)	C++17	70 / 100	1561 ms	184312 KB

chase

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,k,i,a[101010],ta,tb,x[101010],has;
vector<ll> v[101010];
ll d[100010][110];
ll b[100010][110];
ll depe(ll aa,ll bb,ll cc)
{
	if(b[aa][bb]!=i)
	{
		b[aa][bb]=i;
		d[aa][bb]=0;
		ll ii;
		for(ii=0;ii<v[aa].size();ii++)
		{
			if(v[aa][ii]==cc)continue;
			d[aa][bb]=max(d[aa][bb],depe(v[aa][ii],bb,aa));
			if(bb)
				d[aa][bb]=max(d[aa][bb],depe(v[aa][ii],bb-1,aa)+x[aa]-a[cc]);
		}
	}
	return d[aa][bb];
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(i=1;i<=n;i++)
		cin>>a[i];
	for(i=1;i<n;i++)
	{
		cin>>ta>>tb;
		v[ta].pb(tb);
		v[tb].pb(ta);
		x[ta]+=a[tb];
		x[tb]+=a[ta];
	}
	for(i=1;i<=n;i++)
	{
		has=max(has,depe(i,k,0));
		if(n>1000)break;
	}
	cout<<has<<"\n";
}

Compilation message

chase.cpp: In function 'll depe(ll, ll, ll)':
chase.cpp:19:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<v[aa].size();ii++)
            ~~^~~~~~~~~~~~~

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2808 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	4 ms	2780 KB	Output is correct
6	Correct	4 ms	2808 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2808 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	4 ms	2780 KB	Output is correct
6	Correct	4 ms	2808 KB	Output is correct
7	Correct	1561 ms	4704 KB	Output is correct
8	Correct	133 ms	4728 KB	Output is correct
9	Correct	44 ms	4472 KB	Output is correct
10	Correct	272 ms	4548 KB	Output is correct
11	Correct	271 ms	4472 KB	Output is correct
12	Correct	238 ms	4472 KB	Output is correct

Subtask #3

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	640 ms	184312 KB	Output is correct
2	Correct	619 ms	184184 KB	Output is correct
3	Correct	223 ms	180484 KB	Output is correct
4	Correct	255 ms	180272 KB	Output is correct
5	Correct	739 ms	180284 KB	Output is correct
6	Correct	596 ms	180400 KB	Output is correct
7	Correct	671 ms	180384 KB	Output is correct

Subtask #4

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2808 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	4 ms	2780 KB	Output is correct
6	Correct	4 ms	2808 KB	Output is correct
7	Correct	1561 ms	4704 KB	Output is correct
8	Correct	133 ms	4728 KB	Output is correct
9	Correct	44 ms	4472 KB	Output is correct
10	Correct	272 ms	4548 KB	Output is correct
11	Correct	271 ms	4472 KB	Output is correct
12	Correct	238 ms	4472 KB	Output is correct
13	Correct	640 ms	184312 KB	Output is correct
14	Correct	619 ms	184184 KB	Output is correct
15	Correct	223 ms	180484 KB	Output is correct
16	Correct	255 ms	180272 KB	Output is correct
17	Correct	739 ms	180284 KB	Output is correct
18	Correct	596 ms	180400 KB	Output is correct
19	Correct	671 ms	180384 KB	Output is correct
20	Incorrect	349 ms	182368 KB	Output isn't correct
21	Halted	0 ms	0 KB	-