oj.uz

Submission #642863

# Submission time Handle Problem Language Result Execution time Memory
642863 2022-09-20T16:40:31 Z Tenis0206 Paths (RMI21_paths) C++11
56 / 100
 600 ms 18380 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

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];

vector<int> v;

int fr[100005];

/*void debug(vector<int> c)
{
    for(auto it : c)
    {
        cerr<<it<<' ';
    }
    cerr<<'\n';
}
*/

void Add(int val)
{
    v.push_back(val);
  //  ++fr[val];
}

void Remove(int val)
{
   // --fr[val];
    for(auto it=v.begin();it!=v.end();it++)
    {
        if(*it==val)
        {
            v.erase(it);
            break;
        }
    }
}

int kmax()
{
    int sum = 0;
    sort(v.begin(),v.end(),greater<int>());
  //  debug(v);
    for(int i=0;i<k && i<v.size();i++)
    {
        sum += v[i];
    }
    return sum;
}

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 'long long int kmax()':
Main.cpp:55:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i=0;i<k && i<v.size();i++)
      |                        ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 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 3 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 5076 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 3 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 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 15 ms 5128 KB Output is correct
9 Correct 10 ms 5204 KB Output is correct
10 Correct 6 ms 5204 KB Output is correct
11 Correct 15 ms 5188 KB Output is correct
12 Correct 7 ms 5076 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 3 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 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 15 ms 5128 KB Output is correct
9 Correct 10 ms 5204 KB Output is correct
10 Correct 6 ms 5204 KB Output is correct
11 Correct 15 ms 5188 KB Output is correct
12 Correct 7 ms 5076 KB Output is correct
13 Correct 60 ms 5264 KB Output is correct
14 Correct 44 ms 5404 KB Output is correct
15 Correct 8 ms 5264 KB Output is correct
16 Correct 59 ms 5400 KB Output is correct
17 Correct 29 ms 5324 KB Output is correct
18 Correct 41 ms 5204 KB Output is correct
19 Correct 54 ms 5316 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 18380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 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 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 15 ms 5128 KB Output is correct
9 Correct 10 ms 5204 KB Output is correct
10 Correct 6 ms 5204 KB Output is correct
11 Correct 15 ms 5188 KB Output is correct
12 Correct 7 ms 5076 KB Output is correct
13 Correct 60 ms 5264 KB Output is correct
14 Correct 44 ms 5404 KB Output is correct
15 Correct 8 ms 5264 KB Output is correct
16 Correct 59 ms 5400 KB Output is correct
17 Correct 29 ms 5324 KB Output is correct
18 Correct 41 ms 5204 KB Output is correct
19 Correct 54 ms 5316 KB Output is correct
20 Execution timed out 1077 ms 18380 KB Time limit exceeded
21 Halted 0 ms 0 KB -