oj.uz

Submission #1034437

# Submission time Handle Problem Language Result Execution time Memory
1034437 2024-07-25T13:49:41 Z ASN49K Paths (RMI21_paths) C++14
56 / 100
 600 ms 19400 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
        {
            assert(non_used.count(x)>0);
            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:155:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  155 | main()
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 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 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 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 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 6 ms 2904 KB Output is correct
9 Correct 5 ms 2904 KB Output is correct
10 Correct 4 ms 2908 KB Output is correct
11 Correct 5 ms 2908 KB Output is correct
12 Correct 4 ms 2908 KB Output is correct

Subtask #4
20.0 / 20.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 19400 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 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 6 ms 2904 KB Output is correct
9 Correct 5 ms 2904 KB Output is correct
10 Correct 4 ms 2908 KB Output is correct
11 Correct 5 ms 2908 KB Output is correct
12 Correct 4 ms 2908 KB Output is correct
13 Correct 13 ms 3164 KB Output is correct
14 Correct 13 ms 3184 KB Output is correct
15 Correct 7 ms 3164 KB Output is correct
16 Correct 14 ms 2908 KB Output is correct
17 Correct 10 ms 2908 KB Output is correct
18 Correct 9 ms 3052 KB Output is correct
19 Correct 11 ms 3148 KB Output is correct
20 Execution timed out 1066 ms 19400 KB Time limit exceeded
21 Halted 0 ms 0 KB -