Submission #48492

#	Time	Username	Problem	Language	Result	Execution time	Memory
48492		WLZ	Paprike (COI18_paprike)	C++17	0 / 100	1083 ms	14844 KiB

paprike

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef long long ll;
const int INF = 1e9;
const int MAXN = 1e5 + 5;
const ll LINF = 1e18;
const double pi = acos(-1);
const double EPS = 1e-9;
template <class T> using MinPQ = priority_queue<T, vector<T>, greater<T>>;
template <class T> using MaxPQ = priority_queue<T>;

int n;
ll k;
vector<ll> a;
vector< vector<int> > g;
bitset<MAXN> used;
vector<int> p;
vector<int> v;
vector<int> h;

ll preCalc(int u, int par) {
    //printf("node %d, parent %d, orig %lld\n", u, par, a[u]);
    p[u] = par;
    for (int& x : g[u]) {
        if (x != par) {
            a[u] += preCalc(x, u);
            //printf("node %d, add var from node %d, updated to %lld\n", u, x, a[u]);
        }
    }
    //printf("node %d, final %lld\n", u, a[u]);
    return a[u];
}

void dfs(int u, ll val) {
    if (u == -1) return;
    a[u] -= val;
    dfs(p[u], val);
}

bool comp(int i, int j) {
    if (a[i] != a[j]) return a[i] < a[j];
    return i < j;
}

void print(vector<ll>& ve) {
    for (ll& x : ve) printf("%lld ", x);
    printf("\n");
}

int main() {
    #ifdef DEBUG
    freopen("in.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    scanf("%d %lld", &n, &k);
    p.assign(n, -1);
    g.assign(n, vector<int>());
    a.assign(n, 0);
    h.assign(n, 0);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]), h[i] = a[i];
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        scanf("%d %d", &x, &y); --x; --y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    preCalc(0, -1);

    for (int i = 0; i < n; i++) {
        v.emplace_back(i);
    }
    int ans = 0;
    while (true) {
        sort(v.begin(), v.end(), comp);
        bool needSplit = false; 
        int idx = -1;
        for (int i = 0; i < n; i++) {
            if (used[v[i]]) {
                continue;
            } 
            if (a[v[i]] <= k) {
                idx = i;
            } else {
                needSplit = true;
                break;
            }
        }
        if (!needSplit) break;
        used[v[idx]] = 1;

        /*printf("ops %d:\n", ans);
        printf("break the link from %d to %d\n",v[idx], p[v[idx]]);
        printf("element to be considered (before):\n");
        for (int j = 0; j < n; j ++) {
            printf("index %d, val %lld\n", v[j], a[v[j]]);
        }*/
        ans++;
        dfs(p[v[idx]], a[v[idx]]);
        /*printf("element to be considered (after):\n");
        for (int j = 0; j < n; j ++) {
            printf("index %d, val %lld\n", v[j], a[v[j]]);
        }*/
        //v.erase(v.begin() + idx);
    }   
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
paprike.cpp:62:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < n; i++) scanf("%lld", &a[i]), h[i] = a[i];
paprike.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y); --x; --y;
         ~~~~~^~~~~~~~~~~~~~~~~

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