oj.uz

답안 #928731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -