oj.uz

Submission #1106517

# Submission time Handle Problem Language Result Execution time Memory
1106517 2024-10-30T14:03:06 Z ASN49K Petrol stations (CEOI24_stations) C++14
100 / 100
 2950 ms 72884 KB 
#include <bits/stdc++.h>
#define int long long
//#warning("nu uita de clear la aint")
using namespace std;
using i64=long long;
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7,inf=1e9+1;
const i64 INF=1e18;
mt19937 rng(69);
const int N=70'000;
namespace aint
{
    const i64 MAX_VAL=1LL*inf*N;
    struct node
    {
        i64 sum;
        node*l,*r;
        node()
        {
            sum=0;
            l=r=nullptr;
        }
    };
    node* root=nullptr;
    void clear(node*& t)
    {
        if(t==nullptr)
        {
            return;
        }
        clear(t->l);
        clear(t->r);
        delete t;
        t=nullptr;
    }
    void clear()
    {
        clear(root);
    }
    i64 get_val(node* t)
    {
        if(t==nullptr)
        {
            return 0;
        }
        return t->sum;
    }
    void update(node*& t,i64 st,i64 dr,i64 poz,i64 val)
    {
        if(t==nullptr)t=new node;
        t->sum+=val;
        if(st==dr)
        {
            return;
        }
        i64 m=(st+dr)/2;
        if(poz<=m)
        {
            update(t->l,st,m,poz,val);
        }
        else
        {
            update(t->r,m+1,dr,poz,val);
        }
    }
    i64 query(node*& t,i64 st,i64 dr,i64 l,i64 r)
    {
        if(t==nullptr || st>r || dr<l)
        {
            return 0;
        }
        if(l<=st && dr<=r)
        {
            return t->sum;
        }
        i64 m=(st+dr)/2;
        return query(t->l,st,m,l,r)+query(t->r,m+1,dr,l,r);
    }

    void update(i64 poz,i64 k)
    {
        update(root,0,MAX_VAL,poz,k);
    }
    i64 query(i64 l,i64 r)
    {
        return query(root,0,MAX_VAL,l,r);
    }
}
struct edge
{
    int to,cost;
};

int n,k;
vector<pair<int,int>>sk;
i64 sol[N],h[N];
int subtree[N],carry[N],comp[N];
vector<edge>adj[N];
bitset<N>viz;

void recalc_dfs(int nod,int tt)
{
    subtree[nod]=1;
    for(auto &v:adj[nod])
    {
        int c=v.to;
        if(c!=tt && !viz[c])
        {
            recalc_dfs(c,nod);
            subtree[nod]+=subtree[c];
        }
    }
}
int get_centroid(int nod,int tt,int goal)
{
    for(auto &v:adj[nod])
    {
        int c=v.to;
        if(c!=tt && !viz[c] && subtree[c]>=goal)
        {
            return get_centroid(c,nod,goal);
        }
    }
    return nod;
}
//sa fac functie recurstiva de insert
void go_up(int nod,int tt)
{
    if(sk.size()<=1)
    {
        comp[nod]=nod;
    }
    else
    {
        comp[nod]=comp[tt];
    }


    sk.push_back({h[nod],nod});
    carry[nod]=subtree[nod]=1;
    for(auto &v:adj[nod])
    {
        int c=v.to;
        if(c!=tt && !viz[c])
        {
            h[c]=h[nod]+v.cost;
            go_up(c,nod);
            subtree[nod]+=subtree[c];
        }
    }
    if(h[nod]>k)
    {
        //next_stop_up
        carry[lower_bound(all(sk) , (pair<int,int>){h[nod]-k,0})->second]+=carry[nod];
    }
    sk.pop_back();
}
void insert(int nod,int tt,int sign)
{
    if(h[nod]>k)
    {
        return;
    }
    aint::update(k-h[nod],sign*carry[nod]);
    for(auto &v:adj[nod])
    {
        int c=v.to;
        if(c!=tt && !viz[c])
        {
            insert(c,nod,sign);
        }
    }
}
void solve(int nod,int tt,int total)
{
    sol[nod]+=1LL*(total-subtree[comp[nod]])*(carry[nod]-1);
    for(auto &v:adj[nod])
    {
        int c=v.to;
        if(c!=tt && !viz[c])
        {
            if(nod==tt)
            {
                insert(c,nod,-1);
            }
            i64 coef=aint::query(h[nod],h[c]-1);
            sol[nod]+=coef*subtree[c];
            aint::update(h[nod]+k,coef);
            solve(c,nod,total);
            aint::update(h[nod]+k,-coef);
            if(nod==tt)
            {
                insert(c,nod,1);
            }
        }
    }
}

void decomp(int nod)
{
    recalc_dfs(nod,nod);
    nod=get_centroid(nod,nod,subtree[nod]/2);
    h[nod]=0;
    go_up(nod,nod);
    insert(nod,nod,1);
    solve(nod,nod,subtree[nod]);
    aint::clear();
    viz[nod]=true;
    for(auto &c:adj[nod])
    {
        if(!viz[c.to])
        {
            decomp(c.to);
        }
    }
}
main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        adj[x].pb({y, z});
        adj[y].pb({x, z});
    }
    decomp(0);
    for (int i = 0; i < n; i++) {
        cout << sol[i] << '\n';
    }
}

Compilation message

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

Subtask #0
0.0 / 0.0

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 7 ms 4944 KB Output is correct
4 Correct 7 ms 4688 KB Output is correct
5 Correct 5 ms 4688 KB Output is correct
6 Correct 9 ms 5076 KB Output is correct
7 Correct 6 ms 4688 KB Output is correct
8 Correct 1 ms 4688 KB Output is correct
9 Correct 7 ms 4688 KB Output is correct
10 Correct 6 ms 4688 KB Output is correct
11 Correct 6 ms 4688 KB Output is correct
12 Correct 6 ms 4688 KB Output is correct
13 Correct 6 ms 4688 KB Output is correct
14 Correct 3 ms 4688 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 662 ms 15700 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 662 ms 15700 KB Output is correct
5 Correct 2171 ms 72884 KB Output is correct
6 Correct 2474 ms 65264 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 578 ms 8940 KB Output is correct
4 Correct 725 ms 15548 KB Output is correct
5 Correct 683 ms 13248 KB Output is correct
6 Correct 1 ms 4852 KB Output is correct
7 Correct 545 ms 9780 KB Output is correct
8 Correct 558 ms 8924 KB Output is correct
9 Correct 552 ms 9744 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 578 ms 8940 KB Output is correct
4 Correct 725 ms 15548 KB Output is correct
5 Correct 683 ms 13248 KB Output is correct
6 Correct 1 ms 4852 KB Output is correct
7 Correct 545 ms 9780 KB Output is correct
8 Correct 558 ms 8924 KB Output is correct
9 Correct 552 ms 9744 KB Output is correct
10 Correct 321 ms 10188 KB Output is correct
11 Correct 401 ms 8704 KB Output is correct
12 Correct 395 ms 9468 KB Output is correct
13 Correct 415 ms 9396 KB Output is correct
14 Correct 406 ms 9288 KB Output is correct
15 Correct 411 ms 9288 KB Output is correct
16 Correct 118 ms 9096 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 7 ms 4944 KB Output is correct
4 Correct 7 ms 4688 KB Output is correct
5 Correct 5 ms 4688 KB Output is correct
6 Correct 9 ms 5076 KB Output is correct
7 Correct 6 ms 4688 KB Output is correct
8 Correct 1 ms 4688 KB Output is correct
9 Correct 7 ms 4688 KB Output is correct
10 Correct 6 ms 4688 KB Output is correct
11 Correct 6 ms 4688 KB Output is correct
12 Correct 6 ms 4688 KB Output is correct
13 Correct 6 ms 4688 KB Output is correct
14 Correct 3 ms 4688 KB Output is correct
15 Correct 1 ms 4688 KB Output is correct
16 Correct 662 ms 15700 KB Output is correct
17 Correct 2171 ms 72884 KB Output is correct
18 Correct 2474 ms 65264 KB Output is correct
19 Correct 578 ms 8940 KB Output is correct
20 Correct 725 ms 15548 KB Output is correct
21 Correct 683 ms 13248 KB Output is correct
22 Correct 1 ms 4852 KB Output is correct
23 Correct 545 ms 9780 KB Output is correct
24 Correct 558 ms 8924 KB Output is correct
25 Correct 552 ms 9744 KB Output is correct
26 Correct 321 ms 10188 KB Output is correct
27 Correct 401 ms 8704 KB Output is correct
28 Correct 395 ms 9468 KB Output is correct
29 Correct 415 ms 9396 KB Output is correct
30 Correct 406 ms 9288 KB Output is correct
31 Correct 411 ms 9288 KB Output is correct
32 Correct 118 ms 9096 KB Output is correct
33 Correct 2950 ms 66648 KB Output is correct
34 Correct 640 ms 27712 KB Output is correct
35 Correct 879 ms 27420 KB Output is correct
36 Correct 849 ms 27144 KB Output is correct
37 Correct 1346 ms 35196 KB Output is correct
38 Correct 1437 ms 35304 KB Output is correct
39 Correct 1358 ms 35048 KB Output is correct
40 Correct 247 ms 40120 KB Output is correct