| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1028427 |
2024-07-19T20:29:02 Z |
Lemser |
Chase (CEOI17_chase) |
C++14 |
|
245 ms |
335736 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
#define pq_min(a) priority_queue<a, vector<a>, greater<a>>
#define fls cout.flush()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using mii = map<ll,ll>;
using lld = long double;
void valid(ll in){cout<<((in)?"YES\n":"NO\n");}
const int N = 1e5 + 7,LOG=19;
vi graph[N];
ll n,V,p[N],pact[N],ans,act,ady[N];
ll dp[N][101][2],dp2[N][101][2];
void dfsans(ll u,ll pa=0){
dp[u][1][1]=ady[u];
dp2[u][1][1]=ady[u];
// dp[u][i] ir de cualquier nodo en subarbol de u -> u, soltando i migajas
// dp2[u][i] ir de u -> cualquier nodo en subarbol de u, soltando i migajas
for(ll v:graph[u]){
if(v==pa)continue;
dfsans(v,u);
fore(i,1,V+1)
ans = max({ans, dp[u][i][1]+dp2[v][V-i][1]-p[u],dp[u][i][1]+dp2[v][V-i][0],dp[u][i][0]+dp2[v][V-i][1]-p[u],dp[u][i][0]+dp2[v][V-i][0]});
// fore(i,1,V+1)
// ans = max({ans, dp[v][i][1]+dp2[u][V-i][1]-p[v],dp[v][i][1]+dp2[u][V-i][0],dp[v][i][0]+dp2[u][V-i][1]-p[v],dp[v][i][0]+dp2[u][V-i][0]});
fore(i,1,V+1){
// en dp1 mi padre es v
dp[u][i][1] = max({dp[u][i][1], dp[v][i-1][1]+ady[u]-p[v], dp[v][i-1][0]+ady[u]-p[v]});
dp[u][i][0] = max({dp[u][i][0], dp[v][i][1], dp[v][i][0]});
// en dp2 u es el padre de v
dp2[u][i][1] = max({dp2[u][i][1], dp2[v][i-1][1]+ady[u]-p[u], dp2[v][i-1][0]+ady[u]});
dp2[u][i][0] = max({dp2[u][i][0], dp2[v][i][1]-p[u], dp2[v][i][0]});
}
}
}
void test_case(){
cin >> n >> V;
fo(i,n)cin>>p[i+1];
fo(i,n-1){
ll a,b;
cin>>a>>b;
graph[a].pb(b);
graph[b].pb(a);
}
fore(i,1,n+1)
for(int v:graph[i])
ady[i]+=p[v];
dfsans(1);
cout<<ans<<endl;
}
int main(){cin.tie(0)->sync_with_stdio(0);
int t=1;
// cin >> t;
while(t--)test_case();
}
Compilation message
chase.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
4 | #pragma GCC optimization ("O3")
|
chase.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
5 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
213 ms |
335736 KB |
Output is correct |
| 2 |
Correct |
233 ms |
335696 KB |
Output is correct |
| 3 |
Correct |
175 ms |
326600 KB |
Output is correct |
| 4 |
Correct |
140 ms |
326308 KB |
Output is correct |
| 5 |
Correct |
245 ms |
326384 KB |
Output is correct |
| 6 |
Correct |
232 ms |
326484 KB |
Output is correct |
| 7 |
Correct |
232 ms |
326224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
