Submission #1159791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159791		gelastropod	Janjetina (COCI21_janjetina)	C++20	0 / 110	0 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    int n, K, x, y, w;
    cin >> n >> K;
    vector<vector<pair<int, int>>> adjlist(n, vector<pair<int, int>>());
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y >> w;
        x--, y--;
        adjlist[x].push_back({y, w});
        adjlist[y].push_back({x, w});
    }
    queue<int> bfs;
    vector<bool> visited(n, false);
    bfs.push(0);
    visited[0] = true;
    vector<vector<pair<int, int>>> p(12, vector<pair<int, int>>(n, {-1, -1}));
    vector<int> depth(n, 0);
    while (!bfs.empty()) {
        int i = bfs.front();
        bfs.pop();
        for (auto j : adjlist[i]) {
            if (!visited[j.first]) {
                bfs.push(j.first);
                visited[j.first] = true;
                p[0][j.first] = {i, j.second};
                depth[j.first] = depth[i] + 1;
            }
        }
    }
    for (int i = 1; i < 12; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i - 1][j].first == -1) continue;
            p[i][j] = {p[i - 1][p[i - 1][j].first].first, max(p[i - 1][j].second, p[i - 1][p[i - 1][j].first].second)};
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int ci = i, cj = j;
            if (depth[ci] < depth[cj]) swap(ci, cj);
            int maxW = 0;
            int l = 0;
            for (int k = 11; k >= 0; k--) {
                if ((depth[ci] - depth[cj]) >= (1LL << k)) {
                    maxW = max(maxW, p[k][ci].second);
                    ci = p[k][ci].first;
                    l += (1LL << k);
                }
            }
            if (ci == cj && maxW - l >= K) {
                ans++;
                continue;
            }
            for (int k = 11; k >= 0; k--) {
                if (p[k][ci].first == p[k][cj].first) continue;
                maxW = max(maxW, p[k][ci].second);
                ci = p[k][ci].first;
                maxW = max(maxW, p[k][cj].second);
                cj = p[k][cj].first;
                l += (1LL << (k + 1));
            }
            maxW = max(maxW, max(p[0][ci].second, p[0][cj].second));
            l += 2;
            if (maxW - l >= K)
                ans++;
        }
    }
    cout << ans << '\n';
}

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