oj.uz

Submission #928733

# Submission time Handle Problem Language Result Execution time Memory
928733 2024-02-17T03:13:51 Z Regulus Chase (CEOI17_chase) C++17
40 / 100
 1831 ms 524288 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 = 1e5+5;
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);
        if (n > 1000) break;
    }

    cout << ans << '\n';

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 4980 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1831 ms 11092 KB Output is correct
8 Correct 1796 ms 10856 KB Output is correct
9 Correct 20 ms 5212 KB Output is correct
10 Correct 54 ms 5468 KB Output is correct
11 Correct 53 ms 5432 KB Output is correct
12 Correct 54 ms 5460 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1718 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 4980 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1831 ms 11092 KB Output is correct
8 Correct 1796 ms 10856 KB Output is correct
9 Correct 20 ms 5212 KB Output is correct
10 Correct 54 ms 5468 KB Output is correct
11 Correct 53 ms 5432 KB Output is correct
12 Correct 54 ms 5460 KB Output is correct
13 Runtime error 1718 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -