oj.uz

Submission #642866

# Submission time Handle Problem Language Result Execution time Memory
642866 2022-09-20T16:59:19 Z Tenis0206 Paths (RMI21_paths) C++11
100 / 100
 520 ms 51824 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

struct Node
{
    Node *st, *dr;
    int val,prior,sz,sum;
};

Node nil;
Node *T = &nil;

mt19937 my_rand(time(NULL));

int n,k;

int Max[100005],Max2[100005],d[100005];

vector<pair<int,int>> Gaux[100005];
vector<int> G[100005];

int l[100005];

int rez[100005];

Node *modfiu(Node *nod, bool care, Node *son)
{
    if(care==0)
    {
        nod -> st = son;
    }
    else
    {
        nod -> dr = son;
    }
    nod -> sz = nod->st->sz + 1 + nod->dr->sz;
    nod -> sum = nod->st->sum + nod->val + nod->dr->sum;
    return nod;
}

Node *join(Node *st, Node *dr)
{
    if(st==&nil)
    {
        return dr;
    }
    if(dr==&nil)
    {
        return st;
    }
    if(st->prior>=dr->prior)
    {
        return modfiu(st,1,join(st->dr,dr));
    }
    return modfiu(dr,0,join(st,dr->st));
}

pair<Node*,Node*> split(Node *nod, int k)
{
    if(nod==&nil)
    {
        return {&nil,&nil};
    }
    if(nod->st->sz>=k)
    {
        auto t = split(nod->st,k);
        return {t.first,modfiu(nod,0,t.second)};
    }
    auto t = split(nod->dr,k - nod->st->sz - 1);
    return {modfiu(nod,1,t.first),t.second};
}

int Search(Node *nod, int val)
{
    if(nod==&nil)
    {
        return 0;
    }
    if(val>=nod->val)
    {
        return nod->st->sz + 1 + Search(nod->dr,val);
    }
    return Search(nod->st,val);
}

void Add(int val)
{
    int poz = Search(T,val);
    auto t = split(T,poz);
    T = join(t.first,join(new Node{&nil,&nil,val,my_rand(),1,val},t.second));
}

void Remove(int val)
{
    int poz = Search(T,val);
    auto t = split(T,poz-1);
    auto t2 = split(t.second,1);
    T = join(t.first,t2.second);
}

int kmax()
{
    auto t = split(T,T -> sz - k);
    int rez = t.second -> sum;
    T = join(t.first,t.second);
    return rez;
}

void preset(int nod, int dad = 0)
{
    for(auto it : Gaux[nod])
    {
        if(it.first==dad)
        {
            continue;
        }
        preset(it.first,nod);
        d[it.first] = it.second;
    }
}

void dfs(int nod, int dad = 0)
{
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        dfs(it,nod);
        if(l[it] + d[it] > l[Max[nod]] + d[Max[nod]])
        {
            Max2[nod] = Max[nod];
            Max[nod] = it;
        }
        else if(l[it] + d[it] > l[Max2[nod]] + d[Max2[nod]])
        {
            Max2[nod] = it;
        }
    }
    l[nod] = l[Max[nod]] + d[Max[nod]];
    for(auto it : G[nod])
    {
        if(it==dad || it==Max[nod])
        {
            continue;
        }
        Add(l[it] + d[it]);
    }
}

void dfs_solve(int nod, int dad = 0, int lsus = 0, bool mergsus = false)
{
    rez[nod] = kmax();
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        if(mergsus)
        {
            int new_l = max(l[it],lsus + d[it]);
            int new_lsus = d[it] + lsus;
            bool new_mergsus = false;
            Remove(lsus);
            Add(new_l);
            Remove(l[it] + d[it]);
            if(new_l!=l[it])
            {
                new_mergsus = true;
                Add(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                new_mergsus = false;
                Add(new_lsus);
            }
            dfs_solve(it,nod,new_lsus,new_mergsus);
            if(new_l!=l[it])
            {
                Remove(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                Remove(new_lsus);
            }
            Add(l[it] + d[it]);
            Remove(new_l);
            Add(lsus);
            continue;
        }
        if(it!=Max[nod])
        {
            int new_l = max(l[it],l[nod] + d[it]);
            int new_lsus = d[it] + l[nod];
            bool new_mergsus = false;
            Remove(l[nod]);
            Add(new_l);
            Remove(l[it] + d[it]);
            if(new_l!=l[it])
            {
                new_mergsus = true;
                Add(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                new_mergsus = false;
                Add(new_lsus);
            }
            dfs_solve(it,nod,new_lsus,new_mergsus);
            if(new_l!=l[it])
            {
                Remove(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                Remove(new_lsus);
            }
            Add(l[it] + d[it]);
            Remove(new_l);
            Add(l[nod]);
            continue;
        }
        if(lsus > l[Max2[nod]] + d[Max2[nod]])
        {
            int new_l = max(l[it],lsus + d[it]);
            int new_lsus = d[it] + lsus;
            bool new_mergsus = false;
            Remove(l[nod]);
            Add(new_l);
            Remove(lsus);
            if(new_l!=l[it])
            {
                new_mergsus = true;
                Add(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                new_mergsus = false;
                Add(lsus + d[it]);
            }
            dfs_solve(it,nod,new_lsus,new_mergsus);
            if(new_l!=l[it])
            {
                Remove(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                Remove(lsus + d[it]);
            }
            Add(lsus);
            Remove(new_l);
            Add(l[nod]);
        }
        else
        {
            int new_l = max(l[it],l[Max2[nod]] + d[Max2[nod]] + d[it]);
            int new_lsus = d[it] + l[Max2[nod]] + d[Max2[nod]];
            bool new_mergsus = false;
            Remove(l[nod]);
            Add(new_l);
            if(Max2[nod])
            {
                Remove(l[Max2[nod]] + d[Max2[nod]]);
            }
            if(new_l!=l[it])
            {
                new_mergsus = true;
                Add(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                new_mergsus = false;
                Add(l[Max2[nod]] + d[Max2[nod]] + d[it]);
            }
            dfs_solve(it,nod,new_lsus,new_mergsus);
            if(new_l!=l[it])
            {
                Remove(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                Remove(l[Max2[nod]] + d[Max2[nod]] + d[it]);
            }
            if(Max2[nod])
            {
                Add(l[Max2[nod]] + d[Max2[nod]]);
            }
            Remove(new_l);
            Add(l[nod]);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
  //  freopen("nr.in","r",stdin);
  //  freopen("nr.out","w",stdout);
    cin>>n>>k;
    for(int i=1; i<n; i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        Gaux[x].push_back({y,c});
        Gaux[y].push_back({x,c});
        G[x].push_back(y);
        G[y].push_back(x);
    }
    preset(1);
    dfs(1);
    Add(l[1]);
    dfs_solve(1);
    for(int i=1; i<=n; i++)
    {
        cout<<rez[i]<<'\n';
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void Add(long long int)':
Main.cpp:92:57: warning: narrowing conversion of 'my_rand.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   92 |     T = join(t.first,join(new Node{&nil,&nil,val,my_rand(),1,val},t.second));
      |                                                  ~~~~~~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 5 ms 5332 KB Output is correct
11 Correct 5 ms 5460 KB Output is correct
12 Correct 5 ms 5460 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 5 ms 5332 KB Output is correct
11 Correct 5 ms 5460 KB Output is correct
12 Correct 5 ms 5460 KB Output is correct
13 Correct 9 ms 5844 KB Output is correct
14 Correct 7 ms 5972 KB Output is correct
15 Correct 7 ms 5844 KB Output is correct
16 Correct 9 ms 5844 KB Output is correct
17 Correct 8 ms 5844 KB Output is correct
18 Correct 6 ms 5588 KB Output is correct
19 Correct 8 ms 5840 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 47116 KB Output is correct
2 Correct 494 ms 51320 KB Output is correct
3 Correct 358 ms 45920 KB Output is correct
4 Correct 512 ms 49132 KB Output is correct
5 Correct 514 ms 50200 KB Output is correct
6 Correct 487 ms 49348 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5120 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 5 ms 5332 KB Output is correct
11 Correct 5 ms 5460 KB Output is correct
12 Correct 5 ms 5460 KB Output is correct
13 Correct 9 ms 5844 KB Output is correct
14 Correct 7 ms 5972 KB Output is correct
15 Correct 7 ms 5844 KB Output is correct
16 Correct 9 ms 5844 KB Output is correct
17 Correct 8 ms 5844 KB Output is correct
18 Correct 6 ms 5588 KB Output is correct
19 Correct 8 ms 5840 KB Output is correct
20 Correct 455 ms 47116 KB Output is correct
21 Correct 494 ms 51320 KB Output is correct
22 Correct 358 ms 45920 KB Output is correct
23 Correct 512 ms 49132 KB Output is correct
24 Correct 514 ms 50200 KB Output is correct
25 Correct 487 ms 49348 KB Output is correct
26 Correct 520 ms 49616 KB Output is correct
27 Correct 484 ms 51220 KB Output is correct
28 Correct 503 ms 51824 KB Output is correct
29 Correct 359 ms 46136 KB Output is correct
30 Correct 505 ms 49620 KB Output is correct
31 Correct 477 ms 47572 KB Output is correct
32 Correct 487 ms 50568 KB Output is correct
33 Correct 490 ms 49708 KB Output is correct
34 Correct 288 ms 45692 KB Output is correct
35 Correct 488 ms 49584 KB Output is correct
36 Correct 393 ms 51340 KB Output is correct