oj.uz

Submission #382013

# Submission time Handle Problem Language Result Execution time Memory
382013 2021-03-26T09:28:49 Z topovik Janjetina (COCI21_janjetina) C++14
15 / 110
 1500 ms 14184 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{
    int l, r;
    tree1 *L, *R;
    int sm;

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

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

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

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

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

    tree(int _l, int _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;
        int mdl = (l + r) >> 1;
        if (L == NULL) L = new tree(l, mdl);
        if (R == NULL) R = new tree(mdl + 1, r);
    }

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

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

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

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

int Find_Centroid(int x, int y)
{
    for (int 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(int x, int y, int sz, int mx, vector <pair<int, int> > *push)
{
    if (mrk[x]) return;
    push -> pb({sz, mx});
    for (int 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(int x)
{
    vector <pair<int, int> > val[a[x].size()];
    int m = a[x].size();
    for (int i = 0; i < m; i++) Rec(a[x][i], x, 1, b[x][i], &val[i]);
    tree *root = new tree(0, N);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < val[i].size(); j++)
            for (int i1 = 0; i1 < i; i1++)
                for (int j1 = 0; j1 < val[i1].size(); j1++)
                  if (max(val[i][j].s, val[i1][j1].s) - val[i][j].f - val[i1][j1].f >= k) ans++;
    }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < val[i].size(); j++) ans += ((val[i][j].s - val[i][j].f) >= k);
}

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

int main()
{
    int n;
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++)
    {
        int 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 'int Kol(int, int)':
Main.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for (int i = 0; i < a[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'int Find_Centroid(int, int)':
Main.cpp:126:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for (int i = 0; i < a[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void Rec(int, int, int, int, std::vector<std::pair<int, int> >*)':
Main.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = 0; i < a[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void Calc_Ans(int)':
Main.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for (int j = 0; j < val[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
Main.cpp:149:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |                 for (int j1 = 0; j1 < val[i1].size(); j1++)
      |                                  ~~~^~~~~~~~~~~~~~~~
Main.cpp:153:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |         for (int j = 0; j < val[i].size(); j++) ans += ((val[i][j].s - val[i][j].f) >= k);
      |                         ~~^~~~~~~~~~~~~~~
Main.cpp:144:11: warning: unused variable 'root' [-Wunused-variable]
  144 |     tree *root = new tree(0, N);
      |           ^~~~
Main.cpp: In function 'void Centroid(int)':
Main.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int 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 4972 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 6 ms 5228 KB Output is correct
5 Correct 6 ms 5228 KB Output is correct
6 Correct 6 ms 5228 KB Output is correct
7 Correct 6 ms 5228 KB Output is correct
8 Correct 6 ms 5228 KB Output is correct
9 Correct 6 ms 5228 KB Output is correct
10 Correct 6 ms 5228 KB Output is correct
11 Correct 6 ms 5228 KB Output is correct
12 Correct 6 ms 5100 KB Output is correct
13 Correct 6 ms 5100 KB Output is correct
14 Correct 6 ms 5100 KB Output is correct
15 Correct 6 ms 5100 KB Output is correct
16 Correct 6 ms 5228 KB Output is correct
17 Correct 6 ms 5100 KB Output is correct
18 Correct 6 ms 5228 KB Output is correct
19 Correct 6 ms 5100 KB Output is correct
20 Correct 8 ms 5100 KB Output is correct
21 Correct 6 ms 5100 KB Output is correct
22 Correct 6 ms 5228 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 4972 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 6 ms 5228 KB Output is correct
5 Correct 76 ms 6852 KB Output is correct
6 Execution timed out 1519 ms 14184 KB Time limit exceeded
7 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 4972 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 6 ms 5228 KB Output is correct
5 Correct 6 ms 5228 KB Output is correct
6 Correct 6 ms 5228 KB Output is correct
7 Correct 6 ms 5228 KB Output is correct
8 Correct 6 ms 5228 KB Output is correct
9 Correct 6 ms 5228 KB Output is correct
10 Correct 6 ms 5228 KB Output is correct
11 Correct 6 ms 5228 KB Output is correct
12 Correct 6 ms 5100 KB Output is correct
13 Correct 6 ms 5100 KB Output is correct
14 Correct 6 ms 5100 KB Output is correct
15 Correct 6 ms 5100 KB Output is correct
16 Correct 6 ms 5228 KB Output is correct
17 Correct 6 ms 5100 KB Output is correct
18 Correct 6 ms 5228 KB Output is correct
19 Correct 6 ms 5100 KB Output is correct
20 Correct 8 ms 5100 KB Output is correct
21 Correct 6 ms 5100 KB Output is correct
22 Correct 6 ms 5228 KB Output is correct
23 Correct 4 ms 4972 KB Output is correct
24 Correct 4 ms 4972 KB Output is correct
25 Correct 4 ms 5100 KB Output is correct
26 Correct 6 ms 5228 KB Output is correct
27 Correct 76 ms 6852 KB Output is correct
28 Execution timed out 1519 ms 14184 KB Time limit exceeded
29 Halted 0 ms 0 KB -