oj.uz

Submission #1034462

# Submission time Handle Problem Language Result Execution time Memory
1034462 2024-07-25T14:03:01 Z ASN49K Paths (RMI21_paths) C++14
100 / 100
 329 ms 21840 KB 
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7;
struct first_k_sum
{
    int k;
    i64 sum=0;
    multiset<i64>used,non_used;
    void insert(i64 x)
    {
        used.insert(x);
        sum+=x;
        if((int)used.size()>k)
        {
            i64 el=*used.begin();
            sum-=el;
            used.erase(used.find(el));
            non_used.insert(el);
        }
    }
    void erase(i64 x)
    {
        auto it=used.find(x);
        if(it!=used.end())
        {
            sum-=x;
            used.erase(it);
            if(non_used.size())
            {
                i64 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
{
    i64 maxx;
    int 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,i64 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];
i64 rez[N];
Aint aint;
first_k_sum mp;
void change(int poz,i64 val1,i64 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()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    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 2812 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 2812 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 2 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 2812 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 4 ms 2820 KB Output is correct
9 Correct 4 ms 2824 KB Output is correct
10 Correct 4 ms 2908 KB Output is correct
11 Correct 3 ms 2908 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 2812 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 4 ms 2820 KB Output is correct
9 Correct 4 ms 2824 KB Output is correct
10 Correct 4 ms 2908 KB Output is correct
11 Correct 3 ms 2908 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 4 ms 2908 KB Output is correct
14 Correct 4 ms 3164 KB Output is correct
15 Correct 4 ms 3160 KB Output is correct
16 Correct 4 ms 2948 KB Output is correct
17 Correct 5 ms 2904 KB Output is correct
18 Correct 4 ms 3072 KB Output is correct
19 Correct 5 ms 2900 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 18932 KB Output is correct
2 Correct 238 ms 20868 KB Output is correct
3 Correct 212 ms 18772 KB Output is correct
4 Correct 230 ms 19024 KB Output is correct
5 Correct 222 ms 19792 KB Output is correct
6 Correct 248 ms 19080 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 2812 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 4 ms 2820 KB Output is correct
9 Correct 4 ms 2824 KB Output is correct
10 Correct 4 ms 2908 KB Output is correct
11 Correct 3 ms 2908 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 4 ms 2908 KB Output is correct
14 Correct 4 ms 3164 KB Output is correct
15 Correct 4 ms 3160 KB Output is correct
16 Correct 4 ms 2948 KB Output is correct
17 Correct 5 ms 2904 KB Output is correct
18 Correct 4 ms 3072 KB Output is correct
19 Correct 5 ms 2900 KB Output is correct
20 Correct 245 ms 18932 KB Output is correct
21 Correct 238 ms 20868 KB Output is correct
22 Correct 212 ms 18772 KB Output is correct
23 Correct 230 ms 19024 KB Output is correct
24 Correct 222 ms 19792 KB Output is correct
25 Correct 248 ms 19080 KB Output is correct
26 Correct 298 ms 19536 KB Output is correct
27 Correct 261 ms 20820 KB Output is correct
28 Correct 242 ms 21300 KB Output is correct
29 Correct 223 ms 19280 KB Output is correct
30 Correct 329 ms 19320 KB Output is correct
31 Correct 275 ms 18692 KB Output is correct
32 Correct 300 ms 20048 KB Output is correct
33 Correct 264 ms 19420 KB Output is correct
34 Correct 195 ms 18772 KB Output is correct
35 Correct 275 ms 19404 KB Output is correct
36 Correct 253 ms 21840 KB Output is correct