oj.uz

Submission #987580

# Submission time Handle Problem Language Result Execution time Memory
987580 2024-05-23T06:16:28 Z ASN49K Paths (RMI21_paths) C++14
68 / 100
 600 ms 22812 KB 
#include <bits/stdc++.h>

using namespace std;
#define pb      push_back
#define int long long
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;
multiset<int>mp;
void change(int poz,int val1,int val2)
{
    //assert(mp.count(-val1));
    mp.erase(mp.find(-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);
        }
    }
        int old_k=k;
    for(auto &c:mp)
    {
        rez[nod]-=c;
        if(--old_k == 0)
        {
            break;
        }
    }
}
main()
{
    cin>>n>>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:121:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main()
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4960 KB Output is correct
5 Correct 2 ms 4964 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4964 KB Output is correct
8 Correct 4 ms 4956 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct
10 Correct 4 ms 4956 KB Output is correct
11 Correct 4 ms 5056 KB Output is correct
12 Correct 4 ms 4964 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4960 KB Output is correct
5 Correct 2 ms 4964 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4964 KB Output is correct
8 Correct 4 ms 4956 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct
10 Correct 4 ms 4956 KB Output is correct
11 Correct 4 ms 5056 KB Output is correct
12 Correct 4 ms 4964 KB Output is correct
13 Correct 12 ms 5212 KB Output is correct
14 Correct 9 ms 5208 KB Output is correct
15 Correct 7 ms 5212 KB Output is correct
16 Correct 11 ms 5212 KB Output is correct
17 Correct 8 ms 5272 KB Output is correct
18 Correct 5 ms 5208 KB Output is correct
19 Correct 13 ms 5212 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 19448 KB Output is correct
2 Correct 287 ms 22812 KB Output is correct
3 Correct 262 ms 20968 KB Output is correct
4 Correct 294 ms 20940 KB Output is correct
5 Correct 339 ms 22124 KB Output is correct
6 Correct 289 ms 20932 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4960 KB Output is correct
5 Correct 2 ms 4964 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4964 KB Output is correct
8 Correct 4 ms 4956 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct
10 Correct 4 ms 4956 KB Output is correct
11 Correct 4 ms 5056 KB Output is correct
12 Correct 4 ms 4964 KB Output is correct
13 Correct 12 ms 5212 KB Output is correct
14 Correct 9 ms 5208 KB Output is correct
15 Correct 7 ms 5212 KB Output is correct
16 Correct 11 ms 5212 KB Output is correct
17 Correct 8 ms 5272 KB Output is correct
18 Correct 5 ms 5208 KB Output is correct
19 Correct 13 ms 5212 KB Output is correct
20 Correct 315 ms 19448 KB Output is correct
21 Correct 287 ms 22812 KB Output is correct
22 Correct 262 ms 20968 KB Output is correct
23 Correct 294 ms 20940 KB Output is correct
24 Correct 339 ms 22124 KB Output is correct
25 Correct 289 ms 20932 KB Output is correct
26 Execution timed out 1054 ms 20052 KB Time limit exceeded
27 Halted 0 ms 0 KB -