oj.uz

Submission #928735

# Submission time Handle Problem Language Result Execution time Memory
928735 2024-02-17T03:20:46 Z Regulus Chase (CEOI17_chase) C++17
70 / 100
 537 ms 17152 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];
multiset<ll> st;

inline void dfs(int x, int fa)
{
    sum[x] = 0;
    for (int v : g[x]) if (v != fa) sum[x] += a[v];
    st.insert(sum[x]);

    ll tmp = 0, i = 0;
    for (auto it=st.rbegin(); it != st.rend() && i < m; ++it, ++i)
        tmp += *it;
    ans = max(ans, tmp);

    for (int v : g[x])
    {
        if (v == fa) continue;
        dfs(v, x);
    }
    st.erase(st.find(sum[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)
    {
        if (!st.empty()) assert(0);
        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 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 537 ms 2916 KB Output is correct
8 Correct 120 ms 2904 KB Output is correct
9 Correct 50 ms 2648 KB Output is correct
10 Correct 136 ms 2844 KB Output is correct
11 Correct 132 ms 2648 KB Output is correct
12 Correct 124 ms 2652 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 16980 KB Output is correct
2 Correct 124 ms 17152 KB Output is correct
3 Correct 31 ms 10264 KB Output is correct
4 Correct 53 ms 10068 KB Output is correct
5 Correct 56 ms 10188 KB Output is correct
6 Correct 54 ms 10064 KB Output is correct
7 Correct 60 ms 10064 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 537 ms 2916 KB Output is correct
8 Correct 120 ms 2904 KB Output is correct
9 Correct 50 ms 2648 KB Output is correct
10 Correct 136 ms 2844 KB Output is correct
11 Correct 132 ms 2648 KB Output is correct
12 Correct 124 ms 2652 KB Output is correct
13 Correct 111 ms 16980 KB Output is correct
14 Correct 124 ms 17152 KB Output is correct
15 Correct 31 ms 10264 KB Output is correct
16 Correct 53 ms 10068 KB Output is correct
17 Correct 56 ms 10188 KB Output is correct
18 Correct 54 ms 10064 KB Output is correct
19 Correct 60 ms 10064 KB Output is correct
20 Incorrect 45 ms 10064 KB Output isn't correct
21 Halted 0 ms 0 KB -