oj.uz

Submission #878347

# Submission time Handle Problem Language Result Execution time Memory
878347 2023-11-24T08:32:00 Z Mr_Ph Paths (RMI21_paths) C++17
100 / 100
 380 ms 30928 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
ll mod=(ll)1e9+7;
ll mod1=998244353;
///the defines :)
#define endl '\n'
#define vi vector<int>
#define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i];
#define all(arr) arr.begin(),arr.end()
#define allr(arr) arr.rbegin(),arr.rend()
#define sz size()
#define int long long
vector<vector<pair<int,int>>>adj;
int n,k;
int length[200002];
pair<int,int> ans[2][200002];
void dfs(int node,int parent,int w)
{
    // cout<<"HI"<<endl;
    pair<int,int>xd= {0,0};
    for(auto i:adj[node])
    {
        if(i.first==parent)
            continue;
        dfs(i.first,node,i.second);
        // mx.first+=w;
        pair<int,int>mx1=ans[0][i.first];
        mx1.first+=i.second;
        if(mx1>ans[0][node])
            ans[1][node]=ans[0][node],ans[0][node]=mx1;
        else
            ans[1][node]=max(mx1,ans[1][node]);
    }
    if(adj[node].sz==1)
    {
        ans[0][node]= {0,node};
    }
    length[ans[0][node].second]+=w;
}
ordered_set<pair<int,int>>st;
int lol;
int fans[200002];
void re(int x)
{
    int pog=st.order_of_key({length[x],x});
    if(pog>=k)lol-=length[x];
    st.erase({length[x],x});
}
void add(int x,bool del)
{
    st.insert({length[x],x});
    int pog=st.order_of_key({length[x],x});
    if(del){
        if(pog>=k)
            lol+=length[x];
        else lol+=(*st.find_by_order(k)).first;
    }
    else{
        if(pog>=k)
        {
            lol+=length[x];
            if(k>0)
            lol-=(*st.find_by_order(k-1)).first;
        }
    }
}
void dfs1(int node,int parent,int w,pair<int,int>prv)
{
    if(parent!=0){
    prv.first+=w;
    int pog=st.order_of_key({length[ans[0][node].second],ans[0][node].second});
    re(ans[0][node].second);
    length[ans[0][node].second]-=w;
    add(ans[0][node].second,pog>=k);
    fans[node]=lol;
    }
    for(auto i:adj[node])
    {
        if(i.first==parent)continue;
        pair<int,int>nxt=prv;
        if(ans[0][i.first].second==ans[0][node].second)
            nxt=max(ans[1][node],nxt);
        else nxt=max(ans[0][node],nxt);
        int pog=st.order_of_key({length[nxt.second],nxt.second});
        re(nxt.second);
        length[nxt.second]+=i.second;
        add(nxt.second,pog>=k);
        dfs1(i.first,node,i.second,nxt);
        pog=st.order_of_key({length[nxt.second],nxt.second});
        re(nxt.second);
        length[nxt.second]-=i.second;
        add(nxt.second,pog>=k);
    }
    if(parent!=0){
    int pog=st.order_of_key({length[ans[0][node].second],ans[0][node].second});
    re(ans[0][node].second);
    length[ans[0][node].second]+=w;
    add(ans[0][node].second,pog>=k);
    }
}
void preprocess() {}
void solve()
{
    cin>>n>>k;
    adj.resize(n+1);
    for(int i=0; i<n-1; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dfs(1,0,0);
    for(int i=1; i<=n; i++)
        st.insert({length[i],i});
    int cnt=0;
    k=max(0ll,(int)st.sz-k);
    for(auto i:st)
    {
        //cout<<i.first<<" "<<i.second<<endl;
        if(cnt>=k)
            lol+=i.first;
        cnt++;
    }
      fans[1]=lol;
    dfs1(1,0,0,{0,0});
    for(int i=1;i<=n;i++)cout<<fans[i]<<endl;
}
signed main()
{
    // freopen("meta_game_input.txt","r",stdin);
    // freopen("otput.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    preprocess();
    //bla();
    int t=1;
    //cin>>t;
    while(t--)
        solve();
}

Compilation message

Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:26:18: warning: variable 'xd' set but not used [-Wunused-but-set-variable]
   26 |     pair<int,int>xd= {0,0};
      |                  ^~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 6724 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 6724 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct
13 Correct 5 ms 7000 KB Output is correct
14 Correct 4 ms 7004 KB Output is correct
15 Correct 5 ms 7004 KB Output is correct
16 Correct 5 ms 6748 KB Output is correct
17 Correct 5 ms 6748 KB Output is correct
18 Correct 4 ms 6880 KB Output is correct
19 Correct 5 ms 6748 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 25504 KB Output is correct
2 Correct 316 ms 29164 KB Output is correct
3 Correct 336 ms 25696 KB Output is correct
4 Correct 332 ms 25808 KB Output is correct
5 Correct 336 ms 27388 KB Output is correct
6 Correct 344 ms 25748 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 6724 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct
13 Correct 5 ms 7000 KB Output is correct
14 Correct 4 ms 7004 KB Output is correct
15 Correct 5 ms 7004 KB Output is correct
16 Correct 5 ms 6748 KB Output is correct
17 Correct 5 ms 6748 KB Output is correct
18 Correct 4 ms 6880 KB Output is correct
19 Correct 5 ms 6748 KB Output is correct
20 Correct 358 ms 25504 KB Output is correct
21 Correct 316 ms 29164 KB Output is correct
22 Correct 336 ms 25696 KB Output is correct
23 Correct 332 ms 25808 KB Output is correct
24 Correct 336 ms 27388 KB Output is correct
25 Correct 344 ms 25748 KB Output is correct
26 Correct 361 ms 26544 KB Output is correct
27 Correct 344 ms 29132 KB Output is correct
28 Correct 332 ms 30036 KB Output is correct
29 Correct 327 ms 25972 KB Output is correct
30 Correct 340 ms 26060 KB Output is correct
31 Correct 317 ms 25428 KB Output is correct
32 Correct 325 ms 27472 KB Output is correct
33 Correct 338 ms 26180 KB Output is correct
34 Correct 304 ms 26196 KB Output is correct
35 Correct 380 ms 26056 KB Output is correct
36 Correct 341 ms 30928 KB Output is correct