Submission #982137

#TimeUsernameProblemLanguageResultExecution timeMemory
982137Ivo_12Janjetina (COCI21_janjetina)C++98
35 / 110
346 ms22292 KiB
#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, -1); 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:81: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]
   81 |    for(int j = 0; j < querries.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
Main.cpp:85: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]
   85 |    for(int j = 0; j < querries.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...