oj.uz

Submission #602946

# Submission time Handle Problem Language Result Execution time Memory
602946 2022-07-23T13:02:19 Z nguyen31hoang08minh2003 Janjetina (COCI21_janjetina) C++14
15 / 110
 20 ms 5060 KB 
/*
\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/
\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//
/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \
\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /
/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \
\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /
/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \
\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /
//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\
/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\
\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/
\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//
/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \
\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /
/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \
\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /
/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \
\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /
//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\
/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

const int maxN = 100005, ninf = 0xc0c0c0c0;

int n, k;
vii adj[maxN];

void input() {
    int x, y, w;
    cin >> n >> k;
    fore(_, 1, n) {
        cin >> x >> y >> w;
        adj[x].emplace_back(w, y);
        adj[y].emplace_back(w, x);
    }
}

void subtask1() {
    int res = 0;
    const function<void(int, int, int, int)> dfs = [&](int u, int p, int w, int l) {
        if (w - l >= k)
            ++res;
        for (const auto &[h, v] : adj[u]) {
            if (v == p)
                continue;
            dfs(v, u, max(w, h), l + 1);
        }
    };
    fort(u, 1, n)
        dfs(u, -1, ninf, 0);
    cout << res << '\n';
}

void subtask2() {
    /*

        w - l >= k
        w - k >= l

        x + 1 + y = l

    */
    struct DisjointSet {
        std::vector<int> r;
        DisjointSet() {};
        DisjointSet(const int n): r(n, -1) {};
        void reload() {
            std::fill(r.begin(), r.end(), -1);
        };
        int root(const int x) {
            return r[x] < 0 ? x : (r[x] = root(r[x]));
        }
        bool unite(int x, int y) {
            x = root(x);
            y = root(y);
            if (x == y)
                return false;
            if (r[x] > r[y])
                std::swap(x, y);
            r[x] += r[y];
            r[y] = x;
            return true;
        }
        bool connected(const int x, const int y) {
            return root(x) == root(y);
        }
        int treeSize(const int x) {
            return -r[root(x)];
        }
    } dsu(maxN);
    vector<array<int, 3> > edges;
    ll res = 0;
    const function<ll(ll, ll)> sumOfNumbers = [](ll l, ll r) -> ll {
        return (r - l + 1) * (l + r) >> 1;
    };
    fort(u, 1, n)
        for (const auto &[w, v] : adj[u])
            if (u < v)
                edges.pb({w, u, v});
    sort(all(edges));
    for (const auto &[w, x, y] : edges) {
        const ll a = dsu.treeSize(x), b = dsu.treeSize(y);
        if (a + b - 1 <= w - k)
            res += a * b;
//        else if (a - 1 >= w - k - 1 && b - 1 >= w - k - 1)
        else if (a >= w - k && b >= w - k) {
//            fort(i, 2, w - k + 1)
//                res += i - 1;
            res += sumOfNumbers(1, w - k);
        } else if (a >= w - k) {
//            fort(i, 2, w - k + 1) {
//                if (i <= b)
//                    res += i - 1;
//                else
//                    res += b;
//            }
            res += sumOfNumbers(1, b - 1) + (w - k + 1 - b) * b;
        } else if (b >= w - k) {
            res += sumOfNumbers(1, a - 1) + (w - k + 1 - a) * a;
        } else {
//            fort(i, 2, w - k + 1) {
//                if (i - 1 <= a && i - 1 <= b)
//
//            }
        }
        dsu.unite(x, y);
    }
    cout << res << '\n';
}

bool checkSubtask2() {
    int cnt = 0;
    fort(u, 1, n) {
        if (adj[u].size() == 1)
            continue;
        if (adj[u].size() == 2) {
            if ((++cnt) > 2)
                return false;
        } else
            return false;
    }
    return true;
}

//class DisjointSet {
//private:
//    std::vector<int> r;
//public:
//    DisjointSet() {};
//    DisjointSet(const int n): r(n, -1) {};
//
//    void reload() {
//        std::fill(r.begin(), r.end(), -1);
//    };
//
//    int getRoot(const int x) const {
//        return r[x] < 0 ? x : getRoot(r[x]);
//    }
//
//    bool unite(int x, int y) {
//        x = getRoot(x);
//        y = getRoot(y);
//        if (x == y)
//            return false;
//        if (r[x] > r[y])
//            std::swap(x, y);
//        r[x] += r[y];
//        r[y] = x;
//        return true;
//    }
//
//    bool checkConnected(const int x, const int y) {
//        return getRoot(x) == getRoot(y);
//    }
//
//    int getTreeSize(const int x) {
//        return -r[getRoot(x)];
//    }
//
//} dsu(maxN);

void subtask3() {
    cout << 0 << '\n';
}

int main() {
    #ifdef LOCAL
        freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    input();
    if (n <= 1000)
        subtask1();
    else if (checkSubtask2())
        subtask2();
    else
        subtask3();
    return 0;
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:67:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |         for (const auto &[h, v] : adj[u]) {
      |                          ^
Main.cpp: In function 'void subtask2()':
Main.cpp:121:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |         for (const auto &[w, v] : adj[u])
      |                          ^
Main.cpp:125:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |     for (const auto &[w, x, y] : edges) {
      |                      ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 12 ms 2772 KB Output is correct
5 Correct 12 ms 2824 KB Output is correct
6 Correct 11 ms 2804 KB Output is correct
7 Correct 12 ms 2824 KB Output is correct
8 Correct 12 ms 2772 KB Output is correct
9 Correct 13 ms 2724 KB Output is correct
10 Correct 12 ms 2728 KB Output is correct
11 Correct 12 ms 2720 KB Output is correct
12 Correct 15 ms 2644 KB Output is correct
13 Correct 14 ms 2720 KB Output is correct
14 Correct 14 ms 2724 KB Output is correct
15 Correct 15 ms 2644 KB Output is correct
16 Correct 14 ms 2644 KB Output is correct
17 Correct 15 ms 2644 KB Output is correct
18 Correct 14 ms 2720 KB Output is correct
19 Correct 14 ms 2720 KB Output is correct
20 Correct 14 ms 2716 KB Output is correct
21 Correct 14 ms 2720 KB Output is correct
22 Correct 14 ms 2720 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 12 ms 2828 KB Output is correct
5 Correct 4 ms 3028 KB Output is correct
6 Incorrect 20 ms 5060 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 12 ms 2772 KB Output is correct
5 Correct 12 ms 2824 KB Output is correct
6 Correct 11 ms 2804 KB Output is correct
7 Correct 12 ms 2824 KB Output is correct
8 Correct 12 ms 2772 KB Output is correct
9 Correct 13 ms 2724 KB Output is correct
10 Correct 12 ms 2728 KB Output is correct
11 Correct 12 ms 2720 KB Output is correct
12 Correct 15 ms 2644 KB Output is correct
13 Correct 14 ms 2720 KB Output is correct
14 Correct 14 ms 2724 KB Output is correct
15 Correct 15 ms 2644 KB Output is correct
16 Correct 14 ms 2644 KB Output is correct
17 Correct 15 ms 2644 KB Output is correct
18 Correct 14 ms 2720 KB Output is correct
19 Correct 14 ms 2720 KB Output is correct
20 Correct 14 ms 2716 KB Output is correct
21 Correct 14 ms 2720 KB Output is correct
22 Correct 14 ms 2720 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 12 ms 2828 KB Output is correct
27 Correct 4 ms 3028 KB Output is correct
28 Incorrect 20 ms 5060 KB Output isn't correct
29 Halted 0 ms 0 KB -