Submission #1241491

#TimeUsernameProblemLanguageResultExecution timeMemory
1241491alexaaa트리 (IOI24_tree)C++20
0 / 100
2092 ms15916 KiB
#include<iostream> #include<vector> #include<algorithm> #include "tree.h" using namespace std; vector<int> w; vector<pair<int,int>> children; vector<vector<int>> adj_list; int n; void init(std::vector<int> P, std::vector<int> W){ swap(W,w); n = P.size(); adj_list.assign(P.size(),{}); for(int i = 0; i < P.size(); i ++){ if(P[i] != -1){ adj_list[P[i]].push_back(i); } } for(int i = 0; i < P.size(); i++){ children.push_back({adj_list[i].size(),i}); } sort(children.begin(),children.end()); } long long query(int L, int R){ long long answer = 0; vector<long long> sum(n); for(int i = 0; i < n; i++){ if(children[i].first == 0){ answer += (L * w[children[i].second]); sum[children[i].second] = L; } else{ long long total = 0; int u = children[i].second; for(int j = 0; j < children[i].first; j++){ total += sum[adj_list[u][j]]; } if(total < R){ answer += (0*w[children[i].second]); sum[children[i].second] = total; } else{ int diff = R - total; answer += (abs(diff)*w[children[i].second]); sum[children[i].second] = total + diff; } } } return answer; }
#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...