Submission #381958

#	Time	Username	Problem	Language	Result	Execution time	Memory
381958		topovik	Janjetina (COCI21_janjetina)	C++14	0 / 110	36 ms	20204 KiB

Main

#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 tree1
{
    ll l, r;
    tree1 *L, *R;
    ll sm;

    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);
    }

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

    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 *chain;
    tree(ll _l, ll _r)
    {
        l = _l;
        r = _r;
        L = NULL;
        R = NULL;
        chain = NULL;
    }

    void push()
    {
        if (chain == NULL) chain = new tree1(1, 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 (r < x || l > x) return;
        chain -> insert(y);
        if (l == r) return;
        push();
        L -> insert(x, y);
        R -> insert(x, y);
    }

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


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

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

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> > *vc)
{
    if (mrk[x]) return;
    vc -> 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]), vc);
}

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

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 (stderr)

Main.cpp: In function 'll Kol(ll, ll)':
Main.cpp:122: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]
  122 |     for (ll i = 0; i < a[x].size(); i++)
      |                    ~~^~~~~~~~~~~~~
Main.cpp: In function 'll Find_Centroid(ll, ll)':
Main.cpp:130: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]
  130 |     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:139: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]
  139 |     for (ll i = 0; i < a[x].size(); i++)
      |                    ~~^~~~~~~~~~~~~
Main.cpp: In function 'void Calc_Ans(ll)':
Main.cpp:150: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]
  150 |         for (ll j = 0; j < nom[i].size(); j++) ans += (nom[i][j].s - nom[i][j].f) >= k;
      |                        ~~^~~~~~~~~~~~~~~
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 < nom[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp:157: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]
  157 |         for (ll j = 0; j < nom[i].size(); j++) c -> insert(nom[i][j].f, nom[i][j].s);
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp:162: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]
  162 |         for (ll j = 0; j < nom[i].size(); j++) ans += c -> sum(nom[i][j].s - nom[i][j].f - k, nom[i][j].s);
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp:163: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]
  163 |         for (ll j = 0; j < nom[i].size(); j++) c -> insert(nom[i][j].f, nom[i][j].s);
      |                        ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void Centroid(ll)':
Main.cpp:174: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]
  174 |     for (ll i = 0; i < a[x].size(); i++) Centroid(a[x][i]);
      |                    ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60