Submission #878999

#TimeUsernameProblemLanguageResultExecution timeMemory
878999_anhxinloi_Janjetina (COCI21_janjetina)C++14
0 / 110
3 ms12636 KiB
#include<bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; const int maxn = 2e5 + 5; typedef pair<int, int> pii; int n, k, pa[maxn], child[maxn], ans; vector<pii> adj[maxn], g[maxn]; int bit[2*maxn]; bool check[maxn]; void update(int idx, int val){ for(++idx ; idx <= maxn-1 ; idx += idx&(-idx)) bit[idx] += val; } int get(int idx){ int res = 0; for(++idx ; idx > 0 ; idx -= idx&(-idx)) res += bit[idx]; return res; } int dfs_sz(int u, int par){ child[u] = 1; for(auto z : adj[u]){ auto [w, v] = z; if(v == par || check[v]) continue; child[u] += dfs_sz(v, u); } return child[u]; } int centroid(int u, int par, int sz){ for(auto z : adj[u]){ auto [w, v] = z; if(v == par || check[v]) continue; if(child[v] >= sz / 2) return centroid(v, u, sz); } return u; } void dfs_work(int u, int par, int val, int dist, int top){ g[top].push_back(make_pair(val, dist)); for(auto z : adj[u]){ auto [w, v] = z; if(v == par || check[v]) continue; dfs_work(v, u, max(val, w), dist+1, top); } } void build(int u, int par){ int sz = dfs_sz(u, par); int center = centroid(u, par, sz); pa[center] = u; vector<pii> vec = {}; for(auto z : adj[center]){ auto [w, v] = z; if(check[v]) continue; dfs_work(v, u, w, 1, v); sort(g[v].begin(), g[v].end()); for(auto z : g[v]){ auto [val, dist] = z; int cur = val - dist - k; if(cur >= 0){ ++ans; ans -= get(cur); } update(dist, 1); } for(auto z : g[v]){ auto [val, dist] = z; update(dist, -1); vec.push_back(z); } } sort(vec.begin(), vec.end()); for(auto z : vec){ auto [val, dist] = z; int cur = val - dist - k; if(cur >= 0){ ans += get(cur); } update(dist, 1); } for(auto z : vec){ auto [val, dist] = z; update(dist, -1); } for(auto z : adj[center]){ auto [w, v] = z; g[v].clear(); } check[center] = true; for(auto z : adj[center]){ auto [w, v] = z; if(v == center || check[v]) continue; build(v, center); } } signed main(){ // freopen("love.inp" , "r" , stdin); // freopen("love.out" , "w" , stdout); ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> k; for(int i=1 ; i<n ; ++i){ int u, v, w; cin >> u >> v >> w; adj[u].push_back({w, v}); adj[v].push_back({w, u}); } build(1, -1); cout << ans * 2; }

Compilation message (stderr)

Main.cpp: In function 'long long int dfs_sz(long long int, long long int)':
Main.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |         auto [w, v] = z;
      |              ^
Main.cpp: In function 'long long int centroid(long long int, long long int, long long int)':
Main.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         auto [w, v] = z;
      |              ^
Main.cpp: In function 'void dfs_work(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         auto [w, v] = z;
      |              ^
Main.cpp: In function 'void build(long long int, long long int)':
Main.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |         auto [w, v] = z;
      |              ^
Main.cpp:75:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |             auto [val, dist] = z;
      |                  ^
Main.cpp:85:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |             auto [val, dist] = z;
      |                  ^
Main.cpp:93:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |         auto [val, dist] = z;
      |              ^
Main.cpp:102:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         auto [val, dist] = z;
      |              ^
Main.cpp:107:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |         auto [w, v] = z;
      |              ^
Main.cpp:113:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |         auto [w, v] = z;
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...