oj.uz

Submission #982137

# Submission time Handle Problem Language Result Execution time Memory
982137 2024-05-13T23:52:58 Z Ivo_12 Janjetina (COCI21_janjetina) C++
35 / 110
 346 ms 22292 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, -1);
			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 2 ms 6108 KB Output is correct
2 Correct 2 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 5980 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Correct 3 ms 5976 KB Output is correct
9 Correct 3 ms 5980 KB Output is correct
10 Correct 3 ms 5984 KB Output is correct
11 Incorrect 2 ms 5980 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 2 ms 5724 KB Output is correct
2 Correct 2 ms 5720 KB Output is correct
3 Correct 2 ms 5724 KB Output is correct
4 Correct 4 ms 6056 KB Output is correct
5 Correct 20 ms 7496 KB Output is correct
6 Correct 145 ms 14016 KB Output is correct
7 Correct 244 ms 21876 KB Output is correct
8 Correct 316 ms 22240 KB Output is correct
9 Correct 267 ms 21976 KB Output is correct
10 Correct 318 ms 22088 KB Output is correct
11 Correct 249 ms 21760 KB Output is correct
12 Correct 313 ms 22292 KB Output is correct
13 Correct 264 ms 21988 KB Output is correct
14 Correct 309 ms 22228 KB Output is correct
15 Correct 346 ms 21968 KB Output is correct
16 Correct 313 ms 22080 KB Output is correct
17 Correct 320 ms 22036 KB Output is correct
18 Correct 318 ms 22216 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6108 KB Output is correct
2 Correct 2 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 5980 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Correct 3 ms 5976 KB Output is correct
9 Correct 3 ms 5980 KB Output is correct
10 Correct 3 ms 5984 KB Output is correct
11 Incorrect 2 ms 5980 KB Output isn't correct
12 Halted 0 ms 0 KB -