oj.uz

Submission #382016

# Submission time Handle Problem Language Result Execution time Memory
382016 2021-03-26T09:39:20 Z topovik Janjetina (COCI21_janjetina) C++14
15 / 110
 751 ms 524292 KB 
#include <bits/stdc++.h>
#include <chrono>
#define f first
#define s second
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

namespace RANDOM
{
    ll Time()
    {
        return chrono::system_clock().now().time_since_epoch().count();
    }
    mt19937 rnd(Time());
}
using namespace RANDOM;

const ll N = 1e5 + 100;

struct tree;
struct tree1;

struct tree1{
    ll l, r;
    tree1 *L, *R;
    ll sm;

    tree1(ll _l, ll _r)
    {
        l = _l, r = _r;
        L = NULL;
        R = NULL;
        sm = 0;
    }

    void push()
    {
        if (l == r) return;
        ll mdl = (l + r) >> 1;
        if (L == NULL) L = new tree1(l, mdl);
        if (R == NULL) R = new tree1(mdl + 1, r);
    }

    void insert(ll x)
    {
        push();
        if (l > x || r < x) return;
        sm++;
        if (l == r) return;
        L -> insert(x);
        R -> insert(x);
    }

    ll sum(ll x)
    {
        push();
        if (l > x) return 0;
        if (r <= x) return sm;
        return L -> sum(x) + R -> sum(x);
    }
};

struct tree{
    ll l, r;
    tree *L, *R;
    tree1 *sm = NULL;

    tree(ll _l, ll _r)
    {
        l = _l, r = _r;
        L = NULL;
        R = NULL;
        sm = NULL;
    }

    void push()
    {
        if (sm == NULL) sm = new tree1(0, N);
        if (l == r) return;
        ll mdl = (l + r) >> 1;
        if (L == NULL) L = new tree(l, mdl);
        if (R == NULL) R = new tree(mdl + 1, r);
    }

    void insert(ll x, ll y)
    {
        push();
        if (l > x || r < x) return;
        sm -> insert(y);
        if (l == r) return;
        L -> insert(x, y);
        R -> insert(x, y);
    }

    ll sum(ll x, ll y)
    {
        if (x < 0 || y < 0) return 0;
        push();
        if (l > x) return 0;
        if (r <= x) return sm -> sum(y);
        return L -> sum(x, y) + R -> sum(x, y);
    }
};

vector <ll> a[N];
vector <ll> b[N];
ll sz[N];
bool mrk[N];
ll kol, k;
ll ans = 0;

ll Kol(ll x, ll y)
{
    if (mrk[x]) return 0;
    sz[x] = 1;
    for (ll i = 0; i < a[x].size(); i++)
        if (a[x][i] != y) sz[x] += Kol(a[x][i], x);
    return sz[x];
}

ll Find_Centroid(ll x, ll y)
{
    for (ll i = 0; i < a[x].size(); i++)
        if (a[x][i] != y && !mrk[a[x][i]] && sz[a[x][i]] > kol / 2) return Find_Centroid(a[x][i], x);
    return x;
}

void Rec(ll x, ll y, ll sz, ll mx, vector <pair<ll, ll> > *push)
{
    if (mrk[x]) return;
    push -> pb({sz, mx});
    for (ll i = 0; i < a[x].size(); i++)
        if (a[x][i] != y) Rec(a[x][i], x, sz + 1, max(mx, b[x][i]), push);
}

void Calc_Ans(ll x)
{
    vector <pair<ll, ll> > val[a[x].size()];
    ll m = a[x].size();
    for (ll i = 0; i < m; i++) Rec(a[x][i], x, 1, b[x][i], &val[i]);
    tree *root = new tree(0, N);
    for (ll i = 0; i < m; i++)
    {
        for (ll j = 0; j < val[i].size(); j++) ans += root -> sum(val[i][j].s - val[i][j].f - k, val[i][j].s - 1);
        for (ll j = 0; j < val[i].size(); j++) root -> insert(val[i][j].f, val[i][j].s);
    }
    root = new tree(0, N);
    for (ll i = m - 1; i >= 0; i--)
    {
        for (ll j = 0; j < val[i].size(); j++) ans += root -> sum(val[i][j].s - val[i][j].f - k, val[i][j].s);
        for (ll j = 0; j < val[i].size(); j++) root -> insert(val[i][j].f, val[i][j].s);
    }
    for (ll i = 0; i < m; i++)
        for (ll j = 0; j < val[i].size(); j++) ans += ((val[i][j].s - val[i][j].f) >= k);
}

void Centroid(ll x)
{
    if (mrk[x]) return;
    kol = Kol(x, x);
    x = Find_Centroid(x, x);
    mrk[x] = 1;
    Calc_Ans(x);
    for (ll i = 0; i < a[x].size(); i++) Centroid(a[x][i]);
}

int main()
{
    ll n;
    cin >> n >> k;
    for (ll i = 0; i < n - 1; i++)
    {
        ll x, y, z;
        cin >> x >> y >> z;
        a[--x].pb(--y);
        a[y].pb(x);
        b[x].pb(z);
        b[y].pb(z);
    }
    Centroid(0);
    cout << ans * 2;
}

Compilation message

Main.cpp: In function 'll Kol(ll, ll)':
Main.cpp:120:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (ll i = 0; i < a[x].size(); i++)
      |                    ~~^~~~~~~~~~~~~
Main.cpp: In function 'll Find_Centroid(ll, ll)':
Main.cpp:127:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (ll i = 0; i < a[x].size(); i++)
      |                    ~~^~~~~~~~~~~~~
Main.cpp: In function 'void Rec(ll, ll, ll, ll, std::vector<std::pair<long long int, long long int> >*)':
Main.cpp:136:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (ll i = 0; i < a[x].size(); i++)
      |                    ~~^~~~~~~~~~~~~
Main.cpp: In function 'void Calc_Ans(ll)':
Main.cpp:148:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for (ll j = 0; j < val[i].size(); j++) ans += root -> sum(val[i][j].s - val[i][j].f - k, val[i][j].s - 1);
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp:149:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for (ll j = 0; j < val[i].size(); j++) root -> insert(val[i][j].f, val[i][j].s);
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp:154:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         for (ll j = 0; j < val[i].size(); j++) ans += root -> sum(val[i][j].s - val[i][j].f - k, val[i][j].s);
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp:155:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         for (ll j = 0; j < val[i].size(); j++) root -> insert(val[i][j].f, val[i][j].s);
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp:158:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         for (ll j = 0; j < val[i].size(); j++) ans += ((val[i][j].s - val[i][j].f) >= k);
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void Centroid(ll)':
Main.cpp:168:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |     for (ll i = 0; i < a[x].size(); i++) Centroid(a[x][i]);
      |                    ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 24 ms 19948 KB Output is correct
4 Correct 295 ms 226668 KB Output is correct
5 Correct 161 ms 110592 KB Output is correct
6 Correct 206 ms 144108 KB Output is correct
7 Correct 192 ms 135660 KB Output is correct
8 Correct 262 ms 194284 KB Output is correct
9 Correct 56 ms 35948 KB Output is correct
10 Correct 87 ms 60652 KB Output is correct
11 Correct 122 ms 88044 KB Output is correct
12 Correct 121 ms 83948 KB Output is correct
13 Correct 171 ms 122476 KB Output is correct
14 Correct 216 ms 162668 KB Output is correct
15 Correct 93 ms 62828 KB Output is correct
16 Correct 109 ms 73196 KB Output is correct
17 Correct 114 ms 80492 KB Output is correct
18 Correct 158 ms 114412 KB Output is correct
19 Correct 163 ms 119916 KB Output is correct
20 Correct 148 ms 109676 KB Output is correct
21 Correct 201 ms 152684 KB Output is correct
22 Correct 182 ms 133612 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 5216 KB Output is correct
3 Correct 26 ms 20332 KB Output is correct
4 Correct 307 ms 234348 KB Output is correct
5 Runtime error 751 ms 524292 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 24 ms 19948 KB Output is correct
4 Correct 295 ms 226668 KB Output is correct
5 Correct 161 ms 110592 KB Output is correct
6 Correct 206 ms 144108 KB Output is correct
7 Correct 192 ms 135660 KB Output is correct
8 Correct 262 ms 194284 KB Output is correct
9 Correct 56 ms 35948 KB Output is correct
10 Correct 87 ms 60652 KB Output is correct
11 Correct 122 ms 88044 KB Output is correct
12 Correct 121 ms 83948 KB Output is correct
13 Correct 171 ms 122476 KB Output is correct
14 Correct 216 ms 162668 KB Output is correct
15 Correct 93 ms 62828 KB Output is correct
16 Correct 109 ms 73196 KB Output is correct
17 Correct 114 ms 80492 KB Output is correct
18 Correct 158 ms 114412 KB Output is correct
19 Correct 163 ms 119916 KB Output is correct
20 Correct 148 ms 109676 KB Output is correct
21 Correct 201 ms 152684 KB Output is correct
22 Correct 182 ms 133612 KB Output is correct
23 Correct 4 ms 4972 KB Output is correct
24 Correct 4 ms 5216 KB Output is correct
25 Correct 26 ms 20332 KB Output is correct
26 Correct 307 ms 234348 KB Output is correct
27 Runtime error 751 ms 524292 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -