oj.uz

Submission #1034442

# Submission time Handle Problem Language Result Execution time Memory
1034442 2024-07-25T13:51:22 Z ASN49K Paths (RMI21_paths) C++14
100 / 100
 383 ms 23892 KB 
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define all(x) x.begin(),x.end()
#define pb push_back
#define UNSET -1
#define int long long
const int mod=1e9+7;
struct first_k_sum
{
    int k;
    i64 sum=0;
    multiset<int>used,non_used;
    void insert(int x)
    {
        used.insert(x);
        sum+=x;
        if((int)used.size()>k)
        {
            int el=*used.begin();
            sum-=el;
            used.erase(used.find(el));
            non_used.insert(el);
        }
    }
    void erase(int x)
    {
        auto it=used.find(x);
        if(it!=used.end())
        {
            sum-=x;
            used.erase(it);
            if(non_used.size())
            {
                int val=*non_used.rbegin();
                non_used.erase(non_used.find(val));
                used.insert(val);
                sum+=val;
            }
        }
        else
        {
            non_used.erase(non_used.find(x));
        }
    }
};

struct poz_max
{
    int maxx,poz;
};
poz_max merge(const poz_max& a,const poz_max& b)
{
    if(a.maxx>b.maxx || (a.maxx==b.maxx && a.poz>b.poz))
    {
        return a;
    }
    return b;
}
struct Aint
{
    int n;
    vector<poz_max>aint;
    void update(int poz,int val)
    {
        poz+=n;
        aint[poz].maxx=val;
        for(poz>>=1;poz>0;poz>>=1)
        {
            aint[poz]=merge(aint[poz<<1] , aint[poz<<1|1]);
        }
    }
    poz_max query(int l,int r)
    {
        l+=n;
        r+=n;
        poz_max rez={0,-1};
        while(l<=r)
        {
            if(l&1)rez=merge(rez , aint[l++]);
            if(!(r&1))rez=merge(rez,aint[r--]);
            l>>=1;
            r>>=1;
        }
        return rez;
    }
    void init(int n)
    {
        this->n=n;
        aint=vector<poz_max>(2*n);
        for(int i=0;i<n;i++)
        {
            aint[i+n]={0,i};
        }
    }
    Aint(){}
    Aint(int n)
    {
        init(n);
    }

};
struct Edge
{
    int to,dist;
};
const int N=100'000;
vector<Edge>g[N];
int tin[N],tout[N],rez[N];
Aint aint;
first_k_sum mp;
void change(int poz,int val1,int val2)
{
    mp.erase(val1);
    mp.insert(val2);
    aint.update(poz,val2);
}
void dfs(int nod,int tt)
{
    static int timp=-1;
    tin[nod]=++timp;
    for(auto &c:g[nod])
    {
        if(c.to!=tt)
        {
            dfs(c.to,nod);
            auto it=aint.query(tin[c.to] , tout[c.to]);
            change(it.poz , it.maxx , it.maxx+c.dist);
        }
    }
    tout[nod]=timp;
}
int n,k;
void reroot(int nod,int tt)
{
    for(auto &c:g[nod])
    {
        if(c.to!=tt)
        {
            auto sus=merge(aint.query(0,tin[c.to]-1) , aint.query(tout[c.to]+1 , n-1));
            auto jos=aint.query(tin[c.to] , tout[c.to]);

            change(sus.poz , sus.maxx, sus.maxx+c.dist);
            change(jos.poz , jos.maxx, jos.maxx-c.dist);

            reroot(c.to,nod);

            change(sus.poz , sus.maxx+c.dist , sus.maxx);
            change(jos.poz , jos.maxx-c.dist , jos.maxx);
        }
    }
    rez[nod]=mp.sum;
}
main()
{
    cin>>n>>k;
    mp.k=k;
    aint.init(n);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        x--;
        y--;
        g[x].pb({y,z});
        g[y].pb({x,z});
    }
    for(int i=0;i<n;i++)
    {
        mp.insert(0);
    }
    dfs(0,0);
    reroot(0,0);
    for(int i=0;i<n;i++)
    {
        cout<<rez[i]<<'\n';
    }
    return 0;
}

Compilation message

Main.cpp:154:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  154 | main()
      | ^~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 5 ms 2984 KB Output is correct
10 Correct 4 ms 2908 KB Output is correct
11 Correct 3 ms 2904 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 5 ms 2984 KB Output is correct
10 Correct 4 ms 2908 KB Output is correct
11 Correct 3 ms 2904 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 5 ms 3132 KB Output is correct
14 Correct 5 ms 3164 KB Output is correct
15 Correct 4 ms 2908 KB Output is correct
16 Correct 7 ms 2884 KB Output is correct
17 Correct 5 ms 2908 KB Output is correct
18 Correct 4 ms 2908 KB Output is correct
19 Correct 5 ms 2904 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 19028 KB Output is correct
2 Correct 293 ms 22868 KB Output is correct
3 Correct 265 ms 21032 KB Output is correct
4 Correct 296 ms 20940 KB Output is correct
5 Correct 332 ms 21804 KB Output is correct
6 Correct 302 ms 20940 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 5 ms 2984 KB Output is correct
10 Correct 4 ms 2908 KB Output is correct
11 Correct 3 ms 2904 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 5 ms 3132 KB Output is correct
14 Correct 5 ms 3164 KB Output is correct
15 Correct 4 ms 2908 KB Output is correct
16 Correct 7 ms 2884 KB Output is correct
17 Correct 5 ms 2908 KB Output is correct
18 Correct 4 ms 2908 KB Output is correct
19 Correct 5 ms 2904 KB Output is correct
20 Correct 304 ms 19028 KB Output is correct
21 Correct 293 ms 22868 KB Output is correct
22 Correct 265 ms 21032 KB Output is correct
23 Correct 296 ms 20940 KB Output is correct
24 Correct 332 ms 21804 KB Output is correct
25 Correct 302 ms 20940 KB Output is correct
26 Correct 375 ms 21460 KB Output is correct
27 Correct 353 ms 22748 KB Output is correct
28 Correct 383 ms 23164 KB Output is correct
29 Correct 253 ms 21144 KB Output is correct
30 Correct 328 ms 21668 KB Output is correct
31 Correct 311 ms 20820 KB Output is correct
32 Correct 330 ms 22056 KB Output is correct
33 Correct 284 ms 21508 KB Output is correct
34 Correct 235 ms 21112 KB Output is correct
35 Correct 322 ms 21440 KB Output is correct
36 Correct 345 ms 23892 KB Output is correct