Submission #372892

#	Time	Username	Problem	Language	Result	Execution time	Memory
372892		sam571128	Janjetina (COCI21_janjetina)	C++14	15 / 110	17 ms	6380 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 = 0;
int n,k;
int dis[N], mx[N], bit[N], arr[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){
		res += bit[pos];
		pos -= pos&-pos;
	}
	return res;
}

void dfs(int u, int par){
	for(auto [v,w] : adj[u]){
		if(v==par) continue;
		dis[v] = dis[u]+1;
		mx[v] = max(mx[u],w);
		dfs(v,u);
	}
}

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

void solve(int l, int r){
	if(l >= r) return;
	int mid = l+r>>1;
	solve(l,mid);
	solve(mid+1,r);
	int ma = 0;
	for(int i = mid;i >= l;i--){
		vv.push_back({ma,mid-i});
		ma = max(ma,arr[i-1]);
	}
	ma = 0;
	for(int i = mid;i < r;i++){
		ma = max(ma,arr[i]);
		vv.push_back({ma,i-mid+1});
	}
	solve(1);
	ma = 0;
	for(int i = mid;i >= l;i--){
		vv.push_back({ma,mid-i});
		ma = max(ma,arr[i-1]);
	}
	solve(-1);
	ma = 0;
	for(int i = mid;i < r;i++){
		ma = max(ma,arr[i]);
		vv.push_back({ma,i-mid+1});
	}
	solve(-1);
}

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});
		arr[i] = w;
	}
	if(n <= 1000){
		for(int i = 1;i <= n;i++){
			fill(mx,mx+n+1,0);
			dis[i] = 0;
			dfs(i,-1);
			for(int j = 1;j <= n;j++){
				if(mx[j]-dis[j] >= k&&i!=j){
					ans++;
				}
			}
		}
		cout << ans << "\n";
	}else{
		solve(1,n);
		cout << ans*2 << "\n";
	}
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:34:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |  for(auto [v,w] : adj[u]){
      |           ^
Main.cpp: In function 'void solve(long long int)':
Main.cpp:44:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |  for(auto [a,b] : vv){
      |           ^
Main.cpp:48:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |  for(auto [a,b] : vv){
      |           ^
Main.cpp: In function 'void solve(long long int, long long int)':
Main.cpp:56:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |  int mid = l+r>>1;
      |            ~^~

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