Submission #1185063

#TimeUsernameProblemLanguageResultExecution timeMemory
1185063icebearJanjetina (COCI21_janjetina)C++20
110 / 110
254 ms20104 KiB
// ~~ icebear love attttt ~~ #include <bits/stdc++.h> using namespace std; #define int ll typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class T> bool minimize(T &a, const T &b) { if (a > b) return a = b, true; return false; } template<class T> bool maximize(T &a, const T &b) { if (a < b) return a = b, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "icebearat" const int MOD = 1e9 + 7; const int inf = 1e9 + 27092008; const ll INF = 1e18 + 27092008; const int N = 2e5 + 5; int n, k; vector<ii> G[N]; int ft[N], sz[N]; bool isCentroid[N]; ll ans = 0; vector<ii> global_nodes, internal_nodes; void update(int x, int val) { x++; for(; x < N; x += x & -x) ft[x] += val; } int query(int x) { x++; int res = 0; for(; x; x -= x & -x) res += ft[x]; return res; } void dfs(int u, int par) { sz[u] = 1; for(ii v : G[u]) if (v.fi != par && !isCentroid[v.fi]) { dfs(v.fi, u); sz[u] += sz[v.fi]; } } int findCentroid(int u, int par, const int &subtreeSize) { for(ii v : G[u]) if (v.fi != par && !isCentroid[v.fi] && sz[v.fi] > subtreeSize / 2) return findCentroid(v.fi, u, subtreeSize); return u; } void solve(vector<ii> &nodes, int sign) { ll sum = 0; sort(all(nodes)); for(ii p : nodes) { if (p.fi - p.se >= 0) sum += query(p.fi - p.se); update(p.se, +1); } for(ii p : nodes) update(p.se, -1); ans += sum * sign; } void add_node(int u, int par, int maxW, int depth) { global_nodes.emplace_back(maxW, depth); internal_nodes.emplace_back(maxW, depth); for(ii v : G[u]) if (v.fi != par && !isCentroid[v.fi]) add_node(v.fi, u, max(maxW, v.se), depth + 1); } void buildCentroid(int u) { dfs(u, -1); int centroid = findCentroid(u, -1, sz[u]); global_nodes.emplace_back(0, 0); for(ii v : G[centroid]) if (!isCentroid[v.fi]) { add_node(v.fi, centroid, v.se, 1); solve(internal_nodes, -1); internal_nodes.clear(); } solve(global_nodes, +1); global_nodes.clear(); isCentroid[centroid] = true; for(ii v : G[centroid]) if (!isCentroid[v.fi]) buildCentroid(v.fi); } void init(void) { cin >> n >> k; FOR(i, 2, n) { int u, v, w; cin >> u >> v >> w; w -= k; G[u].pb(mp(v, w)); G[v].pb(mp(u, w)); } } void process(void) { buildCentroid(1); cout << ans * 2; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int tc = 1; // cin >> tc; while(tc--) { init(); process(); } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...