oj.uz

Submission #499718

# Submission time Handle Problem Language Result Execution time Memory
499718 2021-12-29T10:24:04 Z andrei_boaca Paths (RMI21_paths) C++17
36 / 100
 600 ms 19012 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,k,weight[100005],auxw[100005],par[100005],topar[100005],ans,total,tied[100005];
vector<pll> muchii[100005];
vector<int> leaves;
ll bestnode=0;
ll maxim=-1;
ll init[100005],cur[100005],who[100005],c[100005],toprop[100005];
void dfs(ll nod)
{
    init[nod]=0;
    if(muchii[nod].size()==1&&par[nod]!=0)
    {
        init[nod]=1;
        who[nod]=nod;
        leaves.push_back(nod);
        return;
    }
    for(int j=0;j<muchii[nod].size();j++)
    {
        pll i=muchii[nod][j];
        int fiu=i.first;
        int index=i.second;
        if(fiu!=par[nod])
        {
            par[fiu]=nod;
            topar[fiu]=index;
            dfs(fiu);
            init[nod]+=init[fiu];
            if(who[fiu]!=0)
                who[nod]=who[fiu];
        }
    }
    if(init[nod]!=1)
        who[nod]=0;
}
set<pll> s;
void calc(int root)
{
    leaves.clear();
    par[root]=topar[root]=0;
    for(int i=1;i<=n;i++)
    {
        who[i]=0;
        toprop[i]=0;
    }
    s.clear();
    dfs(root);
    ans=total;
    for(int i=1;i<=n;i++)
        cur[i]=init[i];
    for(int j=0;j<leaves.size();j++)
    {
        int i=leaves[j];
        ll cost=0;
        int nod=i;
        while(init[nod]==1&&nod!=root)
        {
            int index=topar[nod];
            cost+=weight[index];
            tied[i]=nod;
            nod=par[nod];
        }
        c[i]=cost;
        s.insert({cost,i});
    }
    ll num=0;
    while(s.size()>k)
    {
        auto it=s.begin();
        ll cost=(*it).first;
        int nod=(*it).second;
        who[nod]=0;
        ans-=cost;
        s.erase(it);
        ll nr=s.size();
        nod=tied[nod];
        cur[nod]=0;
        toprop[nod]=1;
        who[nod]=0;
        while(nod!=root)
        {
            ll p=par[nod];
            cur[p]-=toprop[nod];
            toprop[p]+=toprop[nod];
            toprop[nod]=0;
            if(cur[p]>1)
                break;
            if(cur[p]==0)
                who[p]=0;
            if(cur[p]==1)
            {
                for(int j=0;j<muchii[p].size();j++)
                {
                    pll i=muchii[p][j];
                    int fiu=i.first;
                    if(fiu!=par[p]&&who[fiu]!=0)
                    {
                        who[p]=who[fiu];
                        break;
                    }
                }
                tied[who[p]]=p;
                s.erase({c[who[p]],who[p]});
                c[who[p]]+=weight[topar[p]];
                s.insert({c[who[p]],who[p]});
            }
            nod=p;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        muchii[a].push_back({b,i});
        muchii[b].push_back({a,i});
        weight[i]=auxw[i]=c;
        total+=c;
    }
    for(int root=1;root<=n;root++)
    {
        ans=0;
        calc(root);
        cout<<ans<<'\n';
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(ll)':
Main.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int j=0;j<muchii[nod].size();j++)
      |                 ~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void calc(int)':
Main.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j=0;j<leaves.size();j++)
      |                 ~^~~~~~~~~~~~~~
Main.cpp:71:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   71 |     while(s.size()>k)
      |           ~~~~~~~~^~
Main.cpp:96:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 for(int j=0;j<muchii[p].size();j++)
      |                             ~^~~~~~~~~~~~~~~~~
Main.cpp:79:12: warning: unused variable 'nr' [-Wunused-variable]
   79 |         ll nr=s.size();
      |            ^~
Main.cpp:70:8: warning: unused variable 'num' [-Wunused-variable]
   70 |     ll num=0;
      |        ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct
4 Correct 5 ms 2636 KB Output is correct
5 Correct 5 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 6 ms 2636 KB Output is correct
8 Correct 159 ms 2868 KB Output is correct
9 Correct 70 ms 2916 KB Output is correct
10 Correct 75 ms 2868 KB Output is correct
11 Correct 140 ms 2884 KB Output is correct
12 Correct 90 ms 2844 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct
4 Correct 5 ms 2636 KB Output is correct
5 Correct 5 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 6 ms 2636 KB Output is correct
8 Correct 159 ms 2868 KB Output is correct
9 Correct 70 ms 2916 KB Output is correct
10 Correct 75 ms 2868 KB Output is correct
11 Correct 140 ms 2884 KB Output is correct
12 Correct 90 ms 2844 KB Output is correct
13 Correct 577 ms 3048 KB Output is correct
14 Correct 397 ms 3096 KB Output is correct
15 Correct 255 ms 3128 KB Output is correct
16 Execution timed out 661 ms 3060 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct
4 Correct 5 ms 2636 KB Output is correct
5 Correct 5 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 6 ms 2636 KB Output is correct
8 Correct 159 ms 2868 KB Output is correct
9 Correct 70 ms 2916 KB Output is correct
10 Correct 75 ms 2868 KB Output is correct
11 Correct 140 ms 2884 KB Output is correct
12 Correct 90 ms 2844 KB Output is correct
13 Correct 577 ms 3048 KB Output is correct
14 Correct 397 ms 3096 KB Output is correct
15 Correct 255 ms 3128 KB Output is correct
16 Execution timed out 661 ms 3060 KB Time limit exceeded
17 Halted 0 ms 0 KB -