Submission #372908

#	Time	Username	Problem	Language	Result	Execution time	Memory
372908		sam571128	Janjetina (COCI21_janjetina)	C++14	110 / 110	609 ms	18268 KiB

Main

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e5+5;
vector<pair<int,int>> adj[N];
vector<pair<int,int>> vv;
int ans, nowsz;
int n,k;
int bit[N], sz[N], vis[N], dep[N];

void update(int pos, int val){
	pos++;
	while(pos < N){
		bit[pos] += val;
		pos += pos&-pos;
	}
}

int query(int pos){
	pos++;
	int res = 0;
	while(pos>0){
		res += bit[pos];
		pos -= pos&-pos;
	}
	return res;
}

void dfs(int u, int par){
	nowsz++;
	sz[u] = 1;
	for(auto [v,w] : adj[u]){
		if(v==par||vis[v]) continue;
		dep[v] = dep[u]+1;
		dfs(v,u);
		sz[u] += sz[v];
	}
}

int dfs2(int u, int par){
	for(auto [v,w] : adj[u]){
		if(v==par||vis[v]) continue;
		if(sz[v]*2 > nowsz) return dfs2(v,u);
	}
	return u;
}

void dfs3(int u, int par, int mx){
	vv.push_back({mx,u});
	for(auto [v,w] : adj[u]){
		if(v==par||vis[v]) continue;
		dfs3(v,u,max(mx,w));
	}
}

void solve(int num){
	sort(vv.begin(),vv.end());
	for(auto [a,b] : vv){
		if(a-dep[b]-k>=0) ans += num*query(a-dep[b]-k);
		update(dep[b],1);
	}
	for(auto [a,b] : vv){
		update(dep[b],-1);
	}
	vv.clear();
}

void decompose(int u){
	nowsz = 0;
	dep[u] = 0;
	dfs(u,-1);
	int cen = dfs2(u,-1);
	dep[cen] = 0;
	nowsz = 0;
	dfs(cen,-1);
	dfs3(cen,cen,0);
	solve(1);
	for(auto [v,w] : adj[cen]){
		if(vis[v]) continue;
		dfs3(v,cen,w);
		solve(-1);
	}
	vis[cen] = 1;
	for(auto [v,w] : adj[cen]){
		if(vis[v]) continue;
		decompose(v);
	}
}

signed main(){
	fastio
	cin >> n >> k;
	for(int i = 1;i < n;i++){
		int u,v,w;
		cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	decompose(1);
	cout << ans*2 << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:36:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |  for(auto [v,w] : adj[u]){
      |           ^
Main.cpp: In function 'long long int dfs2(long long int, long long int)':
Main.cpp:45:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |  for(auto [v,w] : adj[u]){
      |           ^
Main.cpp: In function 'void dfs3(long long int, long long int, long long int)':
Main.cpp:54:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |  for(auto [v,w] : adj[u]){
      |           ^
Main.cpp: In function 'void solve(long long int)':
Main.cpp:62:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |  for(auto [a,b] : vv){
      |           ^
Main.cpp:66:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |  for(auto [a,b] : vv){
      |           ^
Main.cpp: In function 'void decompose(long long int)':
Main.cpp:82:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |  for(auto [v,w] : adj[cen]){
      |           ^
Main.cpp:88:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |  for(auto [v,w] : adj[cen]){
      |           ^

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