oj.uz

Submission #497968

# Submission time Handle Problem Language Result Execution time Memory
497968 2021-12-24T06:45:58 Z abc864197532 Janjetina (COCI21_janjetina) C++17
110 / 110
 441 ms 22224 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    if (a.empty())
        return o << "{}";
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
    vvv() {}
};
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(args...) void(0)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 1e9 + 7, N = 100010, logN = 17, K = 350, M = N * 40;

int k;
vector <pii> adj[N];
int sz[N];
bool vis[N];

void dfssz(int v, int pa) {
    sz[v] = 1;
    for (auto [u, w] : adj[v]) if (u != pa && !vis[u]) {
        dfssz(u, v);
        sz[v] += sz[u];
    }
}

int dfscen(int v, int pa, int n) {
    for (auto [u, w] : adj[v]) if (u != pa && !vis[u] && sz[u] * 2 > n)
        return dfscen(u, v, n);
    return v;
}

struct BIT {
    int val[N];
    vector <int> move;
    BIT () {
        fill(val, val + N, 0);
    }
    void add(int p, int v) {
        p += 3;
        for (int i = p; i < N; i += i & (-i))
            val[i] += v, move.pb(i);
    }
    int query(int p) {
        p += 3;
        int ans = 0;
        for (int i = p; i > 0; i -= i & (-i))
            ans += val[i];
        return ans;
    }
    void reset() {
        for (int i : move)
            val[i] = 0;
        move.clear();
    }
} bit;

lli ans;
// max(mx[a], mx[b]) - dp[a] >= k + dp[b]
// mx[a] > mx[b] -> mx[a] - dp[a] >= k + dp[b]
// k + dep[b] <= mx[a] - dep[a]

vector <int> all, cc;
int mx[N], dep[N];

lli calc() {
    sort(all(cc), [&](int i, int j) {
        return mx[i] < mx[j];
    });
    lli cur = 0;
    for (int i : cc) {
        cur += bit.query(mx[i] - dep[i]);
        bit.add(k + dep[i], 1);
    }
    bit.reset();
    return cur;
}

void dfsans(int v, int pa) {
    if (~pa)
        cc.pb(v);
    else
        mx[v] = dep[v] = 0;
    for (auto [u, w] : adj[v]) if (u != pa && !vis[u]) {
        mx[u] = max(mx[v], w);
        dep[u] = dep[v] + 1;
        if (mx[u] - dep[u] >= k)
            ans++;
        dfsans(u, v);
        if (pa == -1) {
            ans -= calc();
            for (int i : cc)
                all.pb(i);
            cc.clear();
        }
    }
    if (pa == -1) {
        swap(all, cc);
        ans += calc();
        cc.clear();
    }
}

void dfscd(int v, int pa) {
    dfssz(v, pa);
    int c = dfscen(v, pa, sz[v]);
    vis[c] = true;
    dfsans(c, -1);
    for (auto [u, w] : adj[c]) if (!vis[u])
        dfscd(u, c);
}

int main () {
    owo;
    int n;
    cin >> n >> k;
    for (int i = 0, u, v, w; i < n - 1; ++i) {
        cin >> u >> v >> w, --u, --v;
        adj[u].eb(v, w), adj[v].eb(u, w);
    }
    dfscd(0, -1);
    cout << ans * 2 << endl;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 5 ms 3200 KB Output is correct
5 Correct 4 ms 3264 KB Output is correct
6 Correct 4 ms 3208 KB Output is correct
7 Correct 4 ms 3208 KB Output is correct
8 Correct 4 ms 3280 KB Output is correct
9 Correct 2 ms 3204 KB Output is correct
10 Correct 3 ms 3152 KB Output is correct
11 Correct 3 ms 3152 KB Output is correct
12 Correct 4 ms 3204 KB Output is correct
13 Correct 3 ms 3152 KB Output is correct
14 Correct 4 ms 3152 KB Output is correct
15 Correct 4 ms 3152 KB Output is correct
16 Correct 4 ms 3196 KB Output is correct
17 Correct 5 ms 3204 KB Output is correct
18 Correct 4 ms 3152 KB Output is correct
19 Correct 3 ms 3200 KB Output is correct
20 Correct 3 ms 3204 KB Output is correct
21 Correct 3 ms 3204 KB Output is correct
22 Correct 3 ms 3152 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 3 ms 3108 KB Output is correct
4 Correct 5 ms 3280 KB Output is correct
5 Correct 31 ms 4996 KB Output is correct
6 Correct 170 ms 12488 KB Output is correct
7 Correct 112 ms 17356 KB Output is correct
8 Correct 441 ms 22224 KB Output is correct
9 Correct 136 ms 17376 KB Output is correct
10 Correct 424 ms 22136 KB Output is correct
11 Correct 298 ms 21692 KB Output is correct
12 Correct 348 ms 22156 KB Output is correct
13 Correct 339 ms 21820 KB Output is correct
14 Correct 377 ms 22060 KB Output is correct
15 Correct 360 ms 21944 KB Output is correct
16 Correct 369 ms 22120 KB Output is correct
17 Correct 371 ms 22072 KB Output is correct
18 Correct 360 ms 22052 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 5 ms 3200 KB Output is correct
5 Correct 4 ms 3264 KB Output is correct
6 Correct 4 ms 3208 KB Output is correct
7 Correct 4 ms 3208 KB Output is correct
8 Correct 4 ms 3280 KB Output is correct
9 Correct 2 ms 3204 KB Output is correct
10 Correct 3 ms 3152 KB Output is correct
11 Correct 3 ms 3152 KB Output is correct
12 Correct 4 ms 3204 KB Output is correct
13 Correct 3 ms 3152 KB Output is correct
14 Correct 4 ms 3152 KB Output is correct
15 Correct 4 ms 3152 KB Output is correct
16 Correct 4 ms 3196 KB Output is correct
17 Correct 5 ms 3204 KB Output is correct
18 Correct 4 ms 3152 KB Output is correct
19 Correct 3 ms 3200 KB Output is correct
20 Correct 3 ms 3204 KB Output is correct
21 Correct 3 ms 3204 KB Output is correct
22 Correct 3 ms 3152 KB Output is correct
23 Correct 1 ms 3020 KB Output is correct
24 Correct 2 ms 3020 KB Output is correct
25 Correct 3 ms 3108 KB Output is correct
26 Correct 5 ms 3280 KB Output is correct
27 Correct 31 ms 4996 KB Output is correct
28 Correct 170 ms 12488 KB Output is correct
29 Correct 112 ms 17356 KB Output is correct
30 Correct 441 ms 22224 KB Output is correct
31 Correct 136 ms 17376 KB Output is correct
32 Correct 424 ms 22136 KB Output is correct
33 Correct 298 ms 21692 KB Output is correct
34 Correct 348 ms 22156 KB Output is correct
35 Correct 339 ms 21820 KB Output is correct
36 Correct 377 ms 22060 KB Output is correct
37 Correct 360 ms 21944 KB Output is correct
38 Correct 369 ms 22120 KB Output is correct
39 Correct 371 ms 22072 KB Output is correct
40 Correct 360 ms 22052 KB Output is correct
41 Correct 2 ms 3024 KB Output is correct
42 Correct 121 ms 17312 KB Output is correct
43 Correct 397 ms 22128 KB Output is correct
44 Correct 144 ms 17352 KB Output is correct
45 Correct 410 ms 22120 KB Output is correct
46 Correct 328 ms 21632 KB Output is correct
47 Correct 367 ms 22200 KB Output is correct
48 Correct 353 ms 21828 KB Output is correct
49 Correct 364 ms 22096 KB Output is correct
50 Correct 361 ms 21948 KB Output is correct
51 Correct 393 ms 22052 KB Output is correct
52 Correct 129 ms 14708 KB Output is correct
53 Correct 153 ms 15172 KB Output is correct
54 Correct 102 ms 11176 KB Output is correct
55 Correct 148 ms 14720 KB Output is correct
56 Correct 143 ms 14772 KB Output is correct
57 Correct 310 ms 14552 KB Output is correct
58 Correct 307 ms 14908 KB Output is correct
59 Correct 363 ms 19036 KB Output is correct
60 Correct 360 ms 18932 KB Output is correct
61 Correct 341 ms 14888 KB Output is correct
62 Correct 247 ms 14480 KB Output is correct
63 Correct 249 ms 14860 KB Output is correct
64 Correct 292 ms 14808 KB Output is correct
65 Correct 14 ms 3792 KB Output is correct
66 Correct 2 ms 3004 KB Output is correct