oj.uz

Submission #1026881

# Submission time Handle Problem Language Result Execution time Memory
1026881 2024-07-18T12:51:13 Z 12345678 Chase (CEOI17_chase) C++17
100 / 100
 1167 ms 180084 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=105;

#define ll long long

ll n, k, b[nx], u, v, sm[nx], dp[nx][kx], dpr[nx][kx], res, sz[nx], used[nx], mx[nx];
vector<ll> d[nx];

int dfssz(int u, int p)
{
    sz[u]=1;
    for (auto v:d[u]) if (v!=p&&!used[v]) sz[u]+=dfssz(v, u);
    return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto v:d[u]) if (v!=p&&!used[v]&&2*sz[v]>rtsz) return findcentroid(v, u, rtsz);
    return u;
}

void dfsadd(int u, int p)
{
    for (int i=1; i<=k; i++) dp[u][i]=max(dp[p][i], dp[p][i-1]+sm[u]-b[p]), mx[i]=max(mx[i], dp[u][i]);
    for (auto v:d[u]) if (v!=p&&!used[v]) dfsadd(v, u);
}

void dfsquery(int u, int p)
{
    for (int i=1; i<=k; i++) dpr[u][i]=max(dpr[p][i], dpr[p][i-1]+sm[p]-b[u]), res=max(res, dpr[u][i]+mx[k-i]);
    for (int i=0; i<k; i++) res=max(res, dpr[u][i]+sm[u]+mx[k-i-1]);
    for (auto v:d[u]) if (v!=p&&!used[v]) dfsquery(v, u);
}

void decomposition(int u)
{
    u=findcentroid(u, u, dfssz(u, u));
    used[u]=1;
    for (int i=0; i<=k; i++) mx[i]=dp[u][i]=dpr[u][i]=0;
    for (int i=0; i<d[u].size(); i++) if (!used[d[u][i]]) dfsquery(d[u][i], u), dfsadd(d[u][i], u);
    res=max(res, mx[k-1]+sm[u]);
    for (int i=0; i<=k; i++) mx[i]=0;
    for (int i=(int)d[u].size()-1; i>=0; i--) if (!used[d[u][i]]) dfsquery(d[u][i], u), dfsadd(d[u][i], u);
    for (auto v:d[u]) if (!used[v]) decomposition(v);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>b[i];
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u), sm[u]+=b[v], sm[v]+=b[u];
    if (k==0) return cout<<0, 0;
    decomposition(1);
    cout<<res;
}

Compilation message

chase.cpp: In function 'void decomposition(int)':
chase.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=0; i<d[u].size(); i++) if (!used[d[u][i]]) dfsquery(d[u][i], u), dfsadd(d[u][i], u);
      |                   ~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 6744 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 6744 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 7 ms 10984 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10964 KB Output is correct
10 Correct 5 ms 10840 KB Output is correct
11 Correct 4 ms 10844 KB Output is correct
12 Correct 2 ms 10932 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1163 ms 177952 KB Output is correct
2 Correct 1103 ms 177744 KB Output is correct
3 Correct 127 ms 175044 KB Output is correct
4 Correct 125 ms 174832 KB Output is correct
5 Correct 868 ms 174824 KB Output is correct
6 Correct 933 ms 174696 KB Output is correct
7 Correct 827 ms 174672 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 6744 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 7 ms 10984 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10964 KB Output is correct
10 Correct 5 ms 10840 KB Output is correct
11 Correct 4 ms 10844 KB Output is correct
12 Correct 2 ms 10932 KB Output is correct
13 Correct 1163 ms 177952 KB Output is correct
14 Correct 1103 ms 177744 KB Output is correct
15 Correct 127 ms 175044 KB Output is correct
16 Correct 125 ms 174832 KB Output is correct
17 Correct 868 ms 174824 KB Output is correct
18 Correct 933 ms 174696 KB Output is correct
19 Correct 827 ms 174672 KB Output is correct
20 Correct 849 ms 176912 KB Output is correct
21 Correct 26 ms 12636 KB Output is correct
22 Correct 801 ms 176724 KB Output is correct
23 Correct 120 ms 176724 KB Output is correct
24 Correct 824 ms 176724 KB Output is correct
25 Correct 123 ms 176716 KB Output is correct
26 Correct 1138 ms 180084 KB Output is correct
27 Correct 1167 ms 180072 KB Output is correct