oj.uz

Submission #71626

# Submission time Handle Problem Language Result Execution time Memory
71626 2018-08-25T09:06:13 Z miljenko_jabucica Paprike (COI18_paprike) C++14
13 / 100
 197 ms 16584 KB 
#include<bits/stdc++.h>

using namespace std;
int n, k;
int niz [100005];
vector <int> v[100005];
int a[100005];
int b[100005];
int rez = 0;
int dfs(int x, int par){
    int sum = 0;
    vector<int> lj_djeca;
    if (v[x].size() == 1 && x != 1)return niz[x-1];
    for (int i = 0; i < v[x].size(); ++i){
        int node = v[x][i];
        if (node == par)continue;
        int sum2 = dfs(node, x);
        lj_djeca.push_back(sum2);
        sum += sum2;
        ///cout <<node <<" " <<sum[node] <<endl;
    }
    sum += niz[x-1];
    sort(lj_djeca.begin(), lj_djeca.end());
    ///cout <<"x -> " <<x <<endl;
    ///for (int i = 0; i < lj_djeca.size(); ++i)cout <<lj_djeca[i] <<" ";
    ///cout <<endl;
    int i = 0;
    while (sum>k){
        sum -= lj_djeca[i];
        ++i;
        ++rez;
    }
    return sum;
}

int main()
{
    cin >>n >>k;
    for (int i = 0; i < n; ++i)cin >>niz[i];
    for (int i = 0; i < n-1; ++i){
        cin >>a[i] >>b[i];
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    dfs(1, 0);
    cout <<rez;
return 0;
}

Compilation message

paprike.cpp: In function 'int dfs(int, int)':
paprike.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v[x].size(); ++i){
                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 16460 KB Output is correct
2 Correct 167 ms 16460 KB Output is correct
3 Correct 184 ms 16548 KB Output is correct
4 Correct 152 ms 16548 KB Output is correct
5 Correct 141 ms 16548 KB Output is correct
6 Correct 197 ms 16548 KB Output is correct
7 Correct 162 ms 16556 KB Output is correct
8 Correct 132 ms 16584 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -