Submission #833574

#TimeUsernameProblemLanguageResultExecution timeMemory
833574RaulAndrei01Paths (RMI21_paths)C++14
0 / 100
101 ms11060 KiB
#include <iostream> #include <vector> using namespace std; const int NMAX = 1e5 + 2; struct node { int val , pri; node *l , *r; node (int v , int p = -1) { val = v; if (p == -1) pri = rand(); else pri = p; l = 0 , r = 0; } int size; }; struct treap { node* root; treap() { root = 0; } void insert (int val) { node *add = new node(val); _insert(root , add); } void erase (int val) { _erase(root , val); } int size() { if (root == 0) return 0; return root->size; } private: void split (node* root , int val , node* &l , node* &r) { if (root == 0) l = r = 0; else if (root->val <= val) { split(root->r , val , root->r , r); l = root; } else { split(root->l , val , l , root->l); r = root; } update_size(root); } void _insert (node* &root , node* add) { if (root == 0) root = add; else if (add->pri > root->pri) { split (root , add->val , add->l , add->r); root = add; } else _insert(root->val <= add->val ? root->r : root->l , add); update_size(root); } void merge (node* &root , node* l , node* r) { if (l == 0) root = r; else if (r == 0) root = l; else if (l->pri > r->pri) { merge(l->r , l->r , r); root = l; } else { merge(r->l , l , r->l); root = r; } update_size(root); } void _erase (node* &root , int val) { if (root->val == val) { node* newRoot = root; merge(root , root->l , root->r); delete newRoot; } else if (root->val < val) { _erase(root->l , val); } else _erase(root->r , val); update_size(root); } void update_size(node* root) { if (root == 0) return; root->size = 1 + root->l->size + root->r->size; } }; vector<pair<int , int> > adj[NMAX]; treap arb; int up[NMAX] , down[NMAX] , down2[NMAX]; int indDown[NMAX]; void dfs (int nod = 1 , int par = 0) { for (auto& edge : adj[nod]) { int to = edge.first , cost = edge.second; if (to == par) continue; dfs(to , nod); int cand = cost + down[to]; if (cand > down[nod]) { down2[nod] = down[nod]; down[nod] = cand; indDown[nod] = to; } else if (cand > down2[nod]) { down2[nod] = cand; } } } void dfs2 (int nod = 1 , int par = 0) { // cout << nod << ' ' << up[nod] << ":\n"; for (auto& edge : adj[nod]) { int to = edge.first , cost = edge.second; if (to == par) continue; if (to == indDown[nod]) { up[to] = down2[nod] + cost; } else up[to] = down[nod] + cost; // cout << to << ' ' << up[to] << ' ' << cost << '\n'; up[to] = max(up[to] , cost + up[nod]); // cout << up[to] << '\n'; dfs2(to , nod); } } int main () { int n , k; cin >> n >> k; for (int i = 1; i < n; i++) { int x , y , c; cin >> x >> y >> c; adj[x].push_back({y , c}); adj[y].push_back({x , c}); } dfs(); dfs2(); for (int i = 1; i <= n; i++) { cout << max(up[i] , down[i]) << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...