oj.uz

답안 #982732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
982732 2024-05-14T16:47:25 Z vjudge1 Chase (CEOI17_chase) C++17
0 / 100
 31 ms 8020 KB 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define int long long
#define ff first
#define ss second
using namespace std;

void solve()
{
    int n,br;
    cin >> n >> br;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    vector<vector<int>> tree(n);
    for (int i = 0; i < n-1; i++)
    {
        int a,b;
        cin >> a >> b;
        --a;--b;
        tree[a].push_back(b);
        tree[b].push_back(a);
        
    }
    vector<int> dsum(n,0);
    for (int i = 0; i < n; i++)
        for (auto a : tree[i])
            dsum[i]+=v[a];
    int ans = 0;
    if (n <= 1001)
        for (int i = 0; i < n; i++)
        {
            queue<array<int,3>> bfs;
            bfs.push({i,dsum[i],1});
            vector<bool> vis(n,0);
            vis[i] = 1;
            while (!bfs.empty())
            {
                auto a = bfs.front();
                ans = max(ans,a[1]);
                for (auto u : tree[a[0]])
                {
                    if (!vis[u])
                    {
                        vis[u]  =1;
                        if (a[2]+1 <= br)
                            bfs.push({u,a[1]+dsum[u]-v[a[0]],a[2]+1});
                    }
                }
                bfs.pop();
            }
        }
    else
    {
        int i = 0;
        queue<array<int,3>> bfs;
        bfs.push({i,dsum[i],1});
        vector<bool> vis(n,0);
        vis[i] = 1;
        while (!bfs.empty())
        {
            auto a = bfs.front();
            ans = max(ans,a[1]);
            for (auto u : tree[a[0]])
            {
                if (!vis[u])
                {
                    vis[u]  =1;
                    if (a[2]+1 <= br)
                        bfs.push({u,a[1]+dsum[u]-v[u]-v[a[0]],a[2]+1});
                }
            }
            bfs.pop();
        }
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
   
       solve();
    
    
    
    return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 8020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -