Submission #336064

#TimeUsernameProblemLanguageResultExecution timeMemory
336064saniyar_krmiCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
30 ms29036 KiB
// YOU ONLY GOT ONE SHOT #include <bits/stdc++.h> #define put(x) cerr << #x << ": " << x << '\n' #define line() cerr << "**************\n" //#define F first //#define S second //#define mul(x, y) (((x) * (y)) %mod) #define bit(i, j) (((i)>>(j)) &1) //#define left(id) ((id<<1) + 1) //#define right(id) ((id<<1) + 2) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<pii, int> piii; const int maxn = 2e5 + 10, lg = 21; int n, m; vector <int> G[maxn]; vector <piii> edge[maxn]; ll dp[maxn], sp[maxn][lg], sum[maxn]; int h[maxn], up[maxn][lg]; int st[maxn], ft[maxn], T; vector <int> vec[maxn]; void dfs1(int v, int par){ st[v] = T++; h[v] = h[par] + 1; up[v][0] = par; for(int i=1; i<lg; i++) up[v][i] = up[up[v][i-1]][i-1]; for(int u: G[v]){ if(u == par) continue; dfs1(u, v); } ft[v] = T; vec[h[v]].push_back(ft[v]); } void dfs(int v, int par){ for(int u: G[v]) sum[v] += sum[u]; } int lift(int u, int p){ for(int i=lg-1; i>=0; i--) if(bit(p, i)) u = up[u][i]; return u; } int get(int u, int v){ if(h[u] < h[v]) swap(u, v); u = lift(u, h[u] - h[v]); if(u == v) return u; for(int i=lg-1; i>=0; i--) if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i]; return up[u][0]; } int main(){ // ios_base::sync_with_stdio(false); // cin.tie(0); cout.tie(0); cin >> n >> m; int pi; for(int i=2; i<=n; i++){ cin >> pi; G[i].push_back(pi), G[pi].push_back(i); } h[0] = -1; dfs1(1, 0); int u, v, c; for(int i=0; i<m; i++){ cin >> u >> v >> c; int lca = get(u, v); edge[lca].push_back({{u, v}, c}); } dfs(1, 0); cout << dp[1] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...