Submission #982140

#	Time	Username	Problem	Language	Result	Execution time	Memory
982140		Ivo_12	Janjetina (COCI21_janjetina)	C++98	110 / 110	374 ms	22332 KiB

Main

#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);
			sort(querries.begin(), querries.end());
			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 (stderr)

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:82: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]
   82 |    for(int j = 0; j < querries.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
Main.cpp:86: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]
   86 |    for(int j = 0; j < querries.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~

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