| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 105294 |
2019-04-11T07:01:00 Z |
ryansee |
Chase (CEOI17_chase) |
C++14 |
|
4000 ms |
525312 KB |
#include "bits/stdc++.h"
using namespace std;
#define FAST ios::sync_with_stdio(false); cin.tie(0);
#define ll long long int
#define ld long double
#define pb push_back
#define ins insert
#define ph push
#define mmst(x,v) memset(x,v,sizeof(x))
#define all(x) (x).begin(), (x).end()
#define FOR(i,s,e) for(ll i=s;i<e;i++)
#define cbr cerr << "hi\n"
#define MAXN (100006)
#define LLINF ((long long)1e18)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
ll n, A[MAXN], dp[MAXN][102][3], V,ans, alu[MAXN][102][3];
vector<ll>v[MAXN];
// 0 - went down (aka. kid pressed)
// 1 - ready to go up (aka. pressed)
void up(ll &x, ll y) { x=max(x,y); }
void dfs(ll x, ll p) {
FOR(i,0,V+1) dp[x][i][0]=dp[x][i][1]=-LLINF,alu[x][i][0]=alu[x][i][1]=0;
ll sum = 0; for(auto i:v[x])if(i!=p)sum+=A[i];
//~ if(p == -1) {
//~ dp[x][1][1] = sum; if(V>=1)ans = max(ans,sum);
//~ dp[x][0][1] = 0;
//~ } else {
//~ FOR(i,0,V+1) {
//~ up(dp[x][i][0],dp[p][i][1]);
//~ up(dp[x][i][1],dp[p][i][0]); // np
//~ up(dp[x][i][1],dp[p][i][1]);
//~ if(i>0)up(dp[x][i][1],dp[p][i-1][0]+sum); // press
//~ if(i>0)up(dp[x][i][1],dp[p][i-1][1]+sum);
//~ // up(dp[x][i][2],max({dp[p][i][2],dp[p][i][0]}));
//~ ans=max({ans,dp[x][i][0],dp[x][i][1]});
//~ }
//~ }
if(v[x].size()==1&&p!=-1) { dp[x][1][1] = sum; dp[x][0][1] = 0; if(V>=1)ans=max(ans,sum);}
alu[x][1][1] = sum+A[p]; if(V>=1)ans = max(ans,sum+A[p]);
priority_queue <ll> zero[102], one[102];
for(auto i : v[x]) if(i!=p) {
dfs(i,x); // sum -= A[i];
FOR(b,0,V+1) {
up(dp[x][b][0], dp[i][b][1]); zero[b].ph(dp[i][b][1]);
up(dp[x][b][1], max(dp[i][b][0],dp[i][b][1])); one[b].ph(max({max(dp[i][b][0],dp[i][b][1]), (b>0)?max(dp[i][b-1][0],dp[i][b-1][1])+sum:-LLINF}));
if(b>0)up(dp[x][b][1],max(dp[i][b-1][0],dp[i][b-1][1])+sum);
ans=max({ans,dp[x][b][0],dp[x][b][1]});
}
//~ sum += A[i];
}
//~ 0 - went down
//~ 1 - stayed
if(p!=-1)sum += A[p];
for(auto i : v[x]) if(i!=p) {
sum -= A[i];
FOR(b,0,V+1) {
up(alu[x][b][0],alu[i][b][1]);
up(alu[x][b][1],max(alu[i][b][0],alu[i][b][1]));
if(b>0)up(alu[x][b][1],max(alu[i][b-1][0],alu[i][b-1][1])+sum);
ans=max({ans,alu[x][b][0],alu[x][b][1]});
}
sum += A[i];
}
// if(x==6||x==7) cerr << x << ' ' << alu[x][1][0]
FOR(b,0,V+1)zero[b].ph(-LLINF);
FOR(b,0,V+1)one[b].ph(-LLINF);
for(auto i : v[x]) if(i!=p) { // will be my alu
sum -= A[i];
FOR(b,0,V+1) {
bool zeroneed = 0, oneneed = 0; ll hisdp = max({max(dp[i][b][0],dp[i][b][1]), (b>0)?max(dp[i][b-1][0],dp[i][b-1][1])+sum:-LLINF});
if(zero[b].top() == dp[i][b][1]) { zero[b].pop(); zeroneed = 1; }
if(one[b].top() == hisdp) { one[b].pop(); oneneed = 1; }
ll z0 = alu[i][b][1];
ll o1 = max(alu[i][b][0],alu[i][b][1]);
if(b>0)o1=max(o1,max(alu[i][b-1][0],alu[i][b-1][1])+sum);
// ans=max({ans,z0+zero[b].top(),o1+one[b].top()});
if(zeroneed) zero[b].ph(dp[i][b][1]);
if(oneneed) one[b].ph(hisdp);
}
sum += A[i];
}
return;
}
int main()
{
// freopen("in","r",stdin);
FAST
cin>>n>>V; if(n==1) { cout << 0 << '\n'; return 0; }
FOR(i,1,n+1)cin>>A[i]; for(ll i=0;i<n-1;i++) { ll a, b; cin >> a >> b; v[a].pb(b); v[b].pb(a); }
// ll ans = 0;
FOR(i,1,n+1) {
// if((i>1&&n>1000)||1)break;
// for(ll i=0;i<MAXN;i++) for(ll j=0;j<102;j++) dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=-LLINF;
dfs(i,-1);
// ll ans = 0;
// for(ll i=1;i<=n;i++) for(ll j=0;j<=V;j++)ans=max({ans,dp[i][j][0],dp[i][j][1],dp[i][j][2]});
}
//~ dfs(6,-1);
cout<<ans<<'\n';
}
/*
*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
*
*/
Compilation message
chase.cpp: In function 'void dfs(long long int, long long int)':
chase.cpp:74:7: warning: unused variable 'z0' [-Wunused-variable]
ll z0 = alu[i][b][1];
^~
chase.cpp: In function 'int main()':
chase.cpp:11:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
#define FOR(i,s,e) for(ll i=s;i<e;i++)
^
chase.cpp:91:2: note: in expansion of macro 'FOR'
FOR(i,1,n+1)cin>>A[i]; for(ll i=0;i<n-1;i++) { ll a, b; cin >> a >> b; v[a].pb(b); v[b].pb(a); }
^~~
chase.cpp:91:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
FOR(i,1,n+1)cin>>A[i]; for(ll i=0;i<n-1;i++) { ll a, b; cin >> a >> b; v[a].pb(b); v[b].pb(a); }
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 7 |
Execution timed out |
4091 ms |
10872 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
496 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2816 KB |
Output is correct |
| 7 |
Execution timed out |
4091 ms |
10872 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
