oj.uz

Submission #372906

# Submission time Handle Problem Language Result Execution time Memory
372906 2021-03-02T08:50:18 Z sam571128 Janjetina (COCI21_janjetina) C++14
15 / 110
 1500 ms 4956 KB 
#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] > 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[u] = 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[u] = 1;
	for(auto [v,w] : adj[u]){
		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

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[u]){
      |           ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 111 ms 2924 KB Output is correct
5 Correct 125 ms 2924 KB Output is correct
6 Correct 111 ms 3052 KB Output is correct
7 Correct 109 ms 2924 KB Output is correct
8 Correct 131 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 10 ms 2796 KB Output is correct
13 Correct 10 ms 2796 KB Output is correct
14 Correct 13 ms 2796 KB Output is correct
15 Correct 4 ms 2796 KB Output is correct
16 Correct 4 ms 2816 KB Output is correct
17 Correct 4 ms 2796 KB Output is correct
18 Correct 4 ms 2796 KB Output is correct
19 Correct 5 ms 2796 KB Output is correct
20 Correct 4 ms 2796 KB Output is correct
21 Correct 5 ms 2796 KB Output is correct
22 Correct 4 ms 2796 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 3 ms 2812 KB Output is correct
4 Correct 112 ms 2924 KB Output is correct
5 Execution timed out 1580 ms 4956 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 111 ms 2924 KB Output is correct
5 Correct 125 ms 2924 KB Output is correct
6 Correct 111 ms 3052 KB Output is correct
7 Correct 109 ms 2924 KB Output is correct
8 Correct 131 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 10 ms 2796 KB Output is correct
13 Correct 10 ms 2796 KB Output is correct
14 Correct 13 ms 2796 KB Output is correct
15 Correct 4 ms 2796 KB Output is correct
16 Correct 4 ms 2816 KB Output is correct
17 Correct 4 ms 2796 KB Output is correct
18 Correct 4 ms 2796 KB Output is correct
19 Correct 5 ms 2796 KB Output is correct
20 Correct 4 ms 2796 KB Output is correct
21 Correct 5 ms 2796 KB Output is correct
22 Correct 4 ms 2796 KB Output is correct
23 Correct 2 ms 2796 KB Output is correct
24 Correct 2 ms 2796 KB Output is correct
25 Correct 3 ms 2812 KB Output is correct
26 Correct 112 ms 2924 KB Output is correct
27 Execution timed out 1580 ms 4956 KB Time limit exceeded
28 Halted 0 ms 0 KB -