Submission #1245554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245554		franuch	Tree (IOI24_tree)	C++20	7 / 100	56 ms	18472 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
const ll INF = 1e18;

ll V;
vc<ll> par, wgh;
vc<vc<ll>> g;

ll x = 0, y = 0;

void init(vc<int> P, vc<int> W) {
        par.assign(all(P));
        wgh.assign(all(W));
        V = sz(par);
        g.assign(V, vc<ll>());
        for (ll v = 1; v < V; v++)
                g[par[v]].pub(v);

        for (ll v = 0; v < V; v++) {
                x += abs(sz(g[v]) - 1);
                y += max(0ll, sz(g[v]) - 1);
        }
}

ll query(int _L, int _R) {
        ll L = _L;
        ll R = _R;
        return x * L - min(y * L, R - L);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 7 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19