Submission #833580

#	Time	Username	Problem	Language	Result	Execution time	Memory
833580		RaulAndrei01	Paths (RMI21_paths)	C++14	12 / 100	105 ms	14320 KiB

Main

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
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;
ll up[NMAX] , down[NMAX] , down2[NMAX];
ll 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);
        ll 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';
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32