oj.uz

Submission #860109

# Submission time Handle Problem Language Result Execution time Memory
860109 2023-10-11T16:26:49 Z serifefedartar Janjetina (COCI21_janjetina) C++17
0 / 110
 1500 ms 2676 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 22; 
const ll MAXN = 1e5 + 5;

vector<vector<pair<int,int>>> graph;
int marked[MAXN], sz[MAXN], fen[MAXN], fen_len[MAXN];

void update(int k, int x) {
	if (k < 0)
		return ;
	k++;
	while (k < MAXN) {
		fen[k] += x;
		k += k & -k;
	}
}

void update_len(int k, int x) {
	if (k < 0)
		return ;
	k++;
	while (k < MAXN) {
		fen_len[k] += x;
		k += k & -k;
	}
}

int get(int k) {
	if (k < 0)
		return 0;
	k++;

	int res = 0;
	while (k) {
		res += fen[k];
		k -= k & -k;
	}
	return res;
}

int get_len(int k) {
	if (k < 0)
		return 0;
	k++;

	int res = 0;
	while (k) {
		res += fen_len[k];
		k -= k & -k;
	}
	return res;
}

int get_sz(int node, int parent) {
	sz[node] = 1;
	for (auto u : graph[node]) {
		if (u.f == parent || !marked[u.f])
			continue;
		sz[node] += get_sz(u.f, node); 
	}
	return sz[node];
}

int find_centro(int node, int parent, int n) {
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f] && sz[u.f] * 2 >= n)
			return find_centro(u.f, node, n);
	}
	return node;
}

ll ans = 0;
int k;

void eval(int node, int parent, int mx, int len) {
	ans += get_len(mx - len - k);
	ans += get(MAXN) - get(len + k - 1);

	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f])
			eval(u.f, node, max(mx, u.s), len+1);
	}
}

void add(int node, int parent, int mx, int len) {
	update_len(len, 1);
	update(mx - len, 1);

	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f])
			add(u.f, node, max(mx, u.s), len+1); 
	}
}

void solve(int node, int parent) {
	int n = get_sz(node, parent);
	int centroid = find_centro(node, parent, n);
	marked[centroid] = true;

	memset(fen, 0, sizeof(fen));
	memset(fen_len, 0, sizeof(fen_len));
	update(0, 1);
	update_len(0, 1);
	for (auto u : graph[centroid]) {
		if (!marked[u.f]) {
			eval(u.f, centroid, u.s, 1);
			add(u.f, centroid, u.s, 1);
		}
	}

	for (auto u : graph[centroid]) {
		if (u.f != parent && !marked[u.f])
			solve(u.f, node);
	}
}

int main() {
	fast
	int n;
	cin >> n >> k;

	graph = vector<vector<pair<int,int>>>(n+1, vector<pair<int,int>>());
	for (int i = 1; i < n; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		graph[x].push_back({y, w});
		graph[y].push_back({x, w});
	}
	solve(1, 1);
	cout << ans * 2 << "\n";
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 36 ms 1372 KB Output is correct
5 Correct 29 ms 1116 KB Output is correct
6 Correct 35 ms 1376 KB Output is correct
7 Correct 29 ms 1372 KB Output is correct
8 Correct 35 ms 1372 KB Output is correct
9 Correct 13 ms 1116 KB Output is correct
10 Incorrect 12 ms 1116 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 36 ms 1116 KB Output is correct
5 Execution timed out 1552 ms 2676 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Correct 36 ms 1372 KB Output is correct
5 Correct 29 ms 1116 KB Output is correct
6 Correct 35 ms 1376 KB Output is correct
7 Correct 29 ms 1372 KB Output is correct
8 Correct 35 ms 1372 KB Output is correct
9 Correct 13 ms 1116 KB Output is correct
10 Incorrect 12 ms 1116 KB Output isn't correct
11 Halted 0 ms 0 KB -