Submission #1159827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159827		gohchingjayk	Janjetina (COCI21_janjetina)	C++20	15 / 110	1595 ms	4684 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
constexpr int INF = 1ull << 60;
int N, K;
vector<pair<int, int>> adjlist[100000 + 5];
int pa[100000 + 5];
int weights[100000 + 5];
int rootdist[100000 + 5];

void dfs(int x) {
	for (auto [dst, wgt] : adjlist[x]) {
		if (rootdist[dst] != -1) continue;
		rootdist[dst] = rootdist[x] + 1;
		pa[dst] = x;
		weights[dst] = wgt;
		dfs(dst);
	}
}

pair<int, int> sat(int a, int b) {
	if (rootdist[b] < rootdist[a]) swap(a,b);

	int len = 0;
	int maxw = -1;
	
	while (rootdist[b] > rootdist[a]) {
		len++;
		maxw = max(maxw, weights[b]);
		b = pa[b];
	}
	
	while (a != b) {
		len += 2;
		maxw = max(max(maxw, weights[b]), weights[a]);
		a = pa[a], b = pa[b];
	}
	
	return pair {len, maxw};
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> K;
	for (int i = 0; i < N - 1; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		adjlist[a].emplace_back(pair{b,c});
		adjlist[b].emplace_back(pair{a,c});
	}
	
	memset(rootdist, -1, sizeof(rootdist));
	rootdist[1] = 0;
	dfs(1);
	
	int ans = 0;
	for (int i = 1; i <= N; ++i) {
		for (int j = i + 1; j <= N; ++j) {
			auto [len, maxw] = sat(i, j);
			if (maxw - len >= K) ans += 2;
		}
	}
	cout << ans;
}

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