Submission #602946

#	Time	Username	Problem	Language	Result	Execution time	Memory
602946		nguyen31hoang08minh2003	Janjetina (COCI21_janjetina)	C++14	15 / 110	20 ms	5060 KiB

Main

/*
\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/
\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//
/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \
\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /
/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \
\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /
/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \
\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /
//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\
/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\
\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/\-\//\\//\\/-/
\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//\\--\//\\/--//
/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \/ \---\/---/ \
\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /\  \--/\--/  /
/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \/   \//\\/   \
\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /\   /\\//\   /
/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \/  /--\/--\  \
\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /\ /---/\---\ /
//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\//--/\\//\--\\
/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\/-/\\//\\//\-\
*/
#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 (stderr)

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 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60