oj.uz

Submission #1026873

# Submission time Handle Problem Language Result Execution time Memory
1026873 2024-07-18T12:38:14 Z 12345678 Chase (CEOI17_chase) C++17
30 / 100
 1228 ms 179792 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];
    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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Incorrect 1 ms 10888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Incorrect 1 ms 10888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1228 ms 177744 KB Output is correct
2 Correct 1203 ms 179792 KB Output is correct
3 Correct 118 ms 177008 KB Output is correct
4 Correct 126 ms 176788 KB Output is correct
5 Correct 866 ms 176720 KB Output is correct
6 Correct 904 ms 176920 KB Output is correct
7 Correct 867 ms 176712 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Incorrect 1 ms 10888 KB Output isn't correct
6 Halted 0 ms 0 KB -