oj.uz

Submission #891213

# Submission time Handle Problem Language Result Execution time Memory
891213 2023-12-22T12:06:40 Z cpptowin Chase (CEOI17_chase) C++17
100 / 100
 199 ms 198864 KB 
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf (int)1e18
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
int n,V;
vi ke[maxn];
int p[maxn],s[maxn];
int up[maxn][110],down[maxn][110];
int ans;
void dfs(int u,int parent)
{
    up[u][1] = s[u];
    for(int v : ke[u])
    {
        if(v == parent) continue;
        dfs(v,u);
        fo(i,1,V) ans = max(ans,up[u][i] + down[v][V - i]);
        fo(i,1,V)
        {
            up[u][i] = max({up[u][i],up[v][i],up[v][i - 1] + s[u] - p[v]});
            down[u][i] = max({down[u][i],down[v][i],down[v][i - 1] + s[u] - p[parent]});
        }
    }
    reverse(ke[u].begin(),ke[u].end());
    fo(i,1,V) up[u][i] = 0;
    up[u][1] = s[u];
    for(int v : ke[u])
    {
        if(v == parent) continue;
        fo(i,1,V) ans = max(ans,up[u][i] + down[v][V - i]);
        fo(i,1,V)
        {
            up[u][i] = max({up[u][i],up[v][i],up[v][i - 1] + s[u] - p[v]});
            down[u][i] = max({down[u][i],down[v][i],down[v][i - 1] + s[u] - p[parent]});
        }
    }
}
main()
{
#define name "TASK"
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> V;
    fo(i,1,n) cin >> p[i];
    fo(i,1,n - 1)
    {
        int u,v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
        s[v] += p[u];
        s[u] += p[v];
    }
    dfs(1,0);
    cout << ans;
}

Compilation message

chase.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main()
      | ^~~~
chase.cpp: In function 'int main()':
chase.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
chase.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31580 KB Output is correct
2 Correct 7 ms 31580 KB Output is correct
3 Correct 7 ms 31576 KB Output is correct
4 Correct 6 ms 31580 KB Output is correct
5 Correct 6 ms 31580 KB Output is correct
6 Correct 6 ms 31580 KB Output is correct
7 Correct 7 ms 32088 KB Output is correct
8 Correct 9 ms 32348 KB Output is correct
9 Correct 7 ms 31580 KB Output is correct
10 Correct 8 ms 32348 KB Output is correct
11 Correct 7 ms 32344 KB Output is correct
12 Correct 7 ms 32344 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 171472 KB Output is correct
2 Correct 153 ms 173396 KB Output is correct
3 Correct 139 ms 126144 KB Output is correct
4 Correct 102 ms 196472 KB Output is correct
5 Correct 189 ms 198792 KB Output is correct
6 Correct 182 ms 198788 KB Output is correct
7 Correct 199 ms 198480 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31580 KB Output is correct
2 Correct 7 ms 31580 KB Output is correct
3 Correct 7 ms 31576 KB Output is correct
4 Correct 6 ms 31580 KB Output is correct
5 Correct 6 ms 31580 KB Output is correct
6 Correct 6 ms 31580 KB Output is correct
7 Correct 7 ms 32088 KB Output is correct
8 Correct 9 ms 32348 KB Output is correct
9 Correct 7 ms 31580 KB Output is correct
10 Correct 8 ms 32348 KB Output is correct
11 Correct 7 ms 32344 KB Output is correct
12 Correct 7 ms 32344 KB Output is correct
13 Correct 162 ms 171472 KB Output is correct
14 Correct 153 ms 173396 KB Output is correct
15 Correct 139 ms 126144 KB Output is correct
16 Correct 102 ms 196472 KB Output is correct
17 Correct 189 ms 198792 KB Output is correct
18 Correct 182 ms 198788 KB Output is correct
19 Correct 199 ms 198480 KB Output is correct
20 Correct 183 ms 198484 KB Output is correct
21 Correct 53 ms 125764 KB Output is correct
22 Correct 184 ms 198608 KB Output is correct
23 Correct 93 ms 196412 KB Output is correct
24 Correct 192 ms 198864 KB Output is correct
25 Correct 134 ms 125636 KB Output is correct
26 Correct 173 ms 173444 KB Output is correct
27 Correct 162 ms 173548 KB Output is correct