oj.uz

Submission #982139

# Submission time Handle Problem Language Result Execution time Memory
982139 2024-05-13T23:56:28 Z Ivo_12 Janjetina (COCI21_janjetina) C++
35 / 110
 361 ms 20576 KB 
#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pll pair < ll, ll >

using namespace std;

const int N = 1e5+10;
int n, k;
vector < pll > edges[N];
ll maxmass[N];
ll siz[N];
ll dep[N];
bool rip[N];
ll fenwick[N];
vector < pll > querries;

void add( int x, ll v ) {
	for(x; x < N; x += x & -x) fenwick[x] += v;
	return;
}

ll sum( int x ) {
	ll out = 0;
	for(x; x > 0; x -= x & -x) out += fenwick[x];
	return out;
}

void dfs( int x, int par ) {
	
	if(par!=-1) dep[x] = dep[par] + 1;
	else dep[x] = 0;
	if(par==-1) maxmass[x] = 0;
	siz[x] = 1;
	for(int i = 0; i < (int) edges[x].size(); i++) {
		if(edges[x][i].F != par && !rip[edges[x][i].F]) {
			maxmass[edges[x][i].F] = max(maxmass[x], edges[x][i].S);
			dfs(edges[x][i].F, x);
			siz[x] += siz[edges[x][i].F];
		}
	}
	return;
	
}

int find_centroid( int x, int par, int treesiz ) {
	for(int i = 0; i < (int) edges[x].size(); i++) if(!rip[edges[x][i].F] && siz[edges[x][i].F] > treesiz/2 && edges[x][i].F != par) return find_centroid(edges[x][i].F, x, treesiz);
	return x;
}

void add_to_q( int x, int par ) {
	if(dep[x]!=0) querries.pb(mp(maxmass[x], dep[x]));
	for(int i = 0; i < (int) edges[x].size(); i++) {
		if(edges[x][i].F != par && (!rip[edges[x][i].F])) add_to_q(edges[x][i].F, x);
	}
	return;
}

ll dac( int x ) {
	ll sol = 0;
	dfs(x, -1);
	if(siz[x] == 1) return 0;
	x = find_centroid(x, -1, siz[x]);
	dfs(x, -1);
	add_to_q(x, -1);
	sort(querries.begin(), querries.end());
	for(int i = 0; i < (int) querries.size(); i++) {
		sol += sum(querries[i].F - querries[i].S - k) + (int) (querries[i].F - querries[i].S >= k);
		add(querries[i].S, 1);
	}
	for(int i = 0; i < (int) querries.size(); i++) add(querries[i].S, -1);
	querries.clear();
	rip[x] = 1;
	for(int i = 0; i < (int) edges[x].size(); i++) {
		if(!rip[edges[x][i].F]) {
			add_to_q(edges[x][i].F, x);
			for(int j = 0; j < querries.size(); j++) {
				sol -= sum(querries[j].F - querries[j].S - k);
				add(querries[j].S, 1);
			}
			for(int j = 0; j < querries.size(); j++) {
				add(querries[j].S, -1);
			}
			querries.clear();
			sol += dac(edges[x][i].F);
		}
	}
	return sol;
}

int main( void ) {
	
	FIO
	cin >> n >> k;
	int tempa, tempb, tempc;
	for(int i = 0; i < n - 1; i++) {
		cin >> tempa >> tempb >> tempc;
		edges[--tempa].pb(mp(--tempb, tempc));
		edges[tempb].pb(mp(tempa, tempc));
	}
	cout << dac(0) * 2;
	
	return 0;
}

Compilation message

Main.cpp: In function 'void add(int, long long int)':
Main.cpp:23:6: warning: statement has no effect [-Wunused-value]
   23 |  for(x; x < N; x += x & -x) fenwick[x] += v;
      |      ^
Main.cpp: In function 'long long int sum(int)':
Main.cpp:29:6: warning: statement has no effect [-Wunused-value]
   29 |  for(x; x > 0; x -= x & -x) out += fenwick[x];
      |      ^
Main.cpp: In function 'long long int dac(int)':
Main.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    for(int j = 0; j < querries.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
Main.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int j = 0; j < querries.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 3 ms 5980 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 4 ms 6236 KB Output is correct
7 Correct 4 ms 5980 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Incorrect 2 ms 5724 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 3 ms 5980 KB Output is correct
5 Correct 19 ms 7516 KB Output is correct
6 Correct 141 ms 13268 KB Output is correct
7 Correct 235 ms 20420 KB Output is correct
8 Correct 315 ms 20420 KB Output is correct
9 Correct 254 ms 20340 KB Output is correct
10 Correct 318 ms 20420 KB Output is correct
11 Correct 244 ms 20432 KB Output is correct
12 Correct 303 ms 20424 KB Output is correct
13 Correct 240 ms 20536 KB Output is correct
14 Correct 306 ms 20576 KB Output is correct
15 Correct 361 ms 20416 KB Output is correct
16 Correct 305 ms 20424 KB Output is correct
17 Correct 348 ms 20320 KB Output is correct
18 Correct 316 ms 20424 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 3 ms 5980 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 4 ms 6236 KB Output is correct
7 Correct 4 ms 5980 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5724 KB Output is correct
11 Incorrect 2 ms 5724 KB Output isn't correct
12 Halted 0 ms 0 KB -