Submission #148117

#	Time	Username	Problem	Language	Result	Execution time	Memory
148117		WhipppedCream	Paprike (COI18_paprike)	C++17	100 / 100	119 ms	24692 KiB

paprike

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 1e5+5;
vi adj[maxn];
int c[maxn];
ll sum[maxn];
int k;
bool cmp(int u, int v)
{
    return sum[u]> sum[v];
}
int dfs(int u, int p)
{
    sum[u] = c[u];
    int res = 0;
    vi chil;
    for(auto v : adj[u])
    {
        if(v == p) continue;
        chil.pb(v);
        res += dfs(v, u);
        sum[u] += sum[v];
    }
    sort(chil.begin(), chil.end(), cmp);
    for(auto v : chil)
    {
        if(sum[u]<= k) break;
        res++;
        sum[u] -= sum[v];
    }
    return res;
}
int main()
{
    //#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif
    int n; scanf("%d %d", &n, &k);
    for(int i = 1; i<= n; i++) scanf("%d", c+i);
    for(int i = 0; i< n-1; i++)
    {
        int u, v; scanf("%d %d", &u, &v);
        adj[u].pb(v); adj[v].pb(u);
    }
    printf("%d\n", dfs(1, 0));
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:44:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n; scanf("%d %d", &n, &k);
            ~~~~~^~~~~~~~~~~~~~~~~
paprike.cpp:45:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i<= n; i++) scanf("%d", c+i);
                                ~~~~~^~~~~~~~~~~
paprike.cpp:48:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d %d", &u, &v);
                   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49