oj.uz

Submission #381898

# Submission time Handle Problem Language Result Execution time Memory
381898 2021-03-26T06:40:33 Z kartel Janjetina (COCI21_janjetina) C++14
0 / 110
 1500 ms 9640 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 1e5 + 500;

vector <pii> g[N], vec;

int siz[N], to[N], cntall, n, k, root, f[N];
ll ans;

void upd(int v, int val) {for (; v < N; v = (v | (v + 1))) f[v] += val;}
int get(int v) {int res = 0; for (; v >= 0; v = (v & (v + 1)) - 1) res += f[v]; return res;}

void calc_sizes(int v, int pr) {
    siz[v] = 1;

    for (auto u : g[v]) {
        if (to[u.F] || u.F == pr) {
            continue;
        }

        calc_sizes(u.F, v);
        siz[v] += siz[u.F];
    }
}

int fnd_cent(int v, int pr) {
    int cent = -1;

    for (auto u : g[v]) {
        if (to[u.F] || u.F == pr) {
            continue;
        }

        if (siz[u.F] > siz[root] / 2 && (cent == -1 || siz[cent] < siz[u.F])) {
            cent = u.F;
        }
    }

    if (cent == -1) {
        return v;
    }
    else {
        return fnd_cent(cent, v);
    }
}

void calc(int v, int pr, int mx) {
    if (mx > k) {
        ans += cntall + 1;
    }

    for (auto u : g[v]) {
        if (to[u.F] || u.F == pr) {
            continue;
        }

        calc(u.F, v, max(mx, u.S));
    }
}

void add(int v, int pr, int mx, int l) {
    vec.pb({mx, l});

    if (mx - l - k >= 0) {
        ans -= get(mx - l - k);
    }

    upd(l, 1);

    for (auto u : g[v]) {
        if (to[u.F] || u.F == pr) {
            continue;
        }

        add(u.F, v, max(mx, u.S), l + 1);
    }
    upd(l, -1);
}

void go(int v, int pr) {
    root = v;
    calc_sizes(v, pr);

    int cent = fnd_cent(v, pr);
    to[cent] = 1;

    for (int i = 0; i < N; i++) {
        f[i] = 0;
    }

    vec.clear();

    cntall = 0;
    for (auto u : g[cent]) {
        if (to[u.F]) {
            continue;
        }

        add(u.F, cent, u.S, 1);
    }

    for (int i = 0; i < N; i++) {
        f[i] = 0;
    }

    sort(all(vec));

    for (int i = 0; i < sz(vec); i++) {
        int w1 = vec[i].F;
        int l1 = vec[i].S;

        if (w1 - l1 >= k) {
            ans++;
        }

        if (w1 - l1 - k >= 0) {
            ans += get(w1 - l1 - k);
        }

        upd(l1, 1);
    }
    for (int i = 0; i < sz(vec); i++) {
        upd(vec[i].S, -1);
    }

    for (auto u : g[cent]) {
        if (to[u.F]) {
            continue;
        }

        go(u.F, v);
    }
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();

    cin >> n >> k;

    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        g[v].pb({u, w});
        g[u].pb({v, w});
    }

    go(1, -1);

    cout << ans * 2ll;
}


/*

7
4 6 7 2 3 1 5
*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3200 KB Output is correct
2 Correct 4 ms 3052 KB Output is correct
3 Correct 12 ms 3052 KB Output is correct
4 Correct 102 ms 3180 KB Output is correct
5 Correct 99 ms 3180 KB Output is correct
6 Correct 106 ms 3308 KB Output is correct
7 Correct 104 ms 3180 KB Output is correct
8 Correct 110 ms 3308 KB Output is correct
9 Correct 99 ms 3180 KB Output is correct
10 Incorrect 102 ms 3180 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3052 KB Output is correct
2 Correct 3 ms 3052 KB Output is correct
3 Correct 13 ms 3052 KB Output is correct
4 Correct 101 ms 3180 KB Output is correct
5 Correct 1002 ms 4772 KB Output is correct
6 Execution timed out 1582 ms 9640 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3200 KB Output is correct
2 Correct 4 ms 3052 KB Output is correct
3 Correct 12 ms 3052 KB Output is correct
4 Correct 102 ms 3180 KB Output is correct
5 Correct 99 ms 3180 KB Output is correct
6 Correct 106 ms 3308 KB Output is correct
7 Correct 104 ms 3180 KB Output is correct
8 Correct 110 ms 3308 KB Output is correct
9 Correct 99 ms 3180 KB Output is correct
10 Incorrect 102 ms 3180 KB Output isn't correct
11 Halted 0 ms 0 KB -