Submission #1265012

#TimeUsernameProblemLanguageResultExecution timeMemory
1265012nicolo_010Tree (IOI24_tree)C++20
10 / 100
2094 ms27988 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; template <typename T> using v = vector<T>; using ll = long long; #define rep(i, k, n) for (int i=k; i<n; i++) #define cerr if(0) cerr v<int> p, w; int N; v<v<int>> adj; v<int> leaf; v<int> isleaf; void dfs(int n, int p=-1) { bool can = true; for (auto x : adj[n]) { if (x == p) continue; can = false; dfs(x, n); } if (can) leaf.push_back(n); } void init(std::vector<int> P, std::vector<int> W) { p = P; w = W; N = (int)p.size(); adj.resize(N); rep(i, 1, N) { //cerr << i << endl; adj[P[i]].push_back(i); adj[i].push_back(P[i]); } isleaf.assign(N, 0); dfs(0); for (auto x : leaf) isleaf[x]=1; } long long query(int L, int R) { v<ll> C(N); v<ll> val(N, 0); for (int i=N-1; i>=0; i--) { //cerr << i << endl; if (isleaf[i]) { C[i] = L; val[i] = L; } else { while (val[i] > R) { val[i]--; C[i]--; } } if (i == 0) continue; val[p[i]]+=val[i]; } ll sum=0; rep(i, 0, N) { cerr << C[i] << " "; sum += w[i]*abs(C[i]); } cerr << endl; return sum; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...