oj.uz

Submission #928731

# Submission time Handle Problem Language Result Execution time Memory
928731 2024-02-17T03:10:05 Z Regulus Chase (CEOI17_chase) C++17
40 / 100
 1819 ms 6252 KB 
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define bug(x) cerr << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int N = 1005;
ll a[N], sum[N], ans, m;
vector<ll> g[N], vec[N];

inline void dfs(int x, int fa)
{
    sum[x] = 0;
    for (int v : g[x]) if (v != fa) sum[x] += a[v];
    vec[x].pb(sum[x]);
    sort(all(vec[x]), greater<ll>());
    //debug(x), debug(sum[x]), endl;
    //for (int x : vec[0]) bug(x); endl;

    ll tmp = 0;
    for (int i=0; i < min(SZ(vec[x]), m); ++i) tmp += vec[x][i];
    ans = max(ans, tmp);

    for (int v : g[x])
    {
        if (v == fa) continue;
        vec[v] = vec[x];
        dfs(v, x);
    }
}

int main(void)
{ IO
    int n, i;

    cin >> n >> m;
    for (i=1; i <= n; ++i) cin >> a[i];
    for (i=0; i < n-1; ++i)
    {
        int x, y; cin >> x >> y;
        g[x].pb(y), g[y].pb(x);
    }

    for (i=1; i <= n; ++i)
    {
        for (int j=0; j <= n; ++j) vec[j].clear();
        dfs(i, 0);
    }

    cout << ans << '\n';

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1819 ms 6252 KB Output is correct
8 Correct 1774 ms 6200 KB Output is correct
9 Correct 19 ms 600 KB Output is correct
10 Correct 52 ms 604 KB Output is correct
11 Correct 54 ms 568 KB Output is correct
12 Correct 53 ms 604 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1819 ms 6252 KB Output is correct
8 Correct 1774 ms 6200 KB Output is correct
9 Correct 19 ms 600 KB Output is correct
10 Correct 52 ms 604 KB Output is correct
11 Correct 54 ms 568 KB Output is correct
12 Correct 53 ms 604 KB Output is correct
13 Runtime error 1 ms 604 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -