Submission #1118534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118534		Tenis0206	Petrol stations (CEOI24_stations)	C++11	48 / 100	3515 ms	110892 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 70000;

struct Node
{
    Node *st, *dr;
    int val, cnt, len;
};

Node nil;

int n, k;
vector<pair<int,int>> G[nmax + 5];

int w[nmax + 5], lvl[nmax + 5];
bool sel[nmax + 5];
int sz = 0;

multiset<pair<int,int>> s;

int rez[nmax + 5];

Node *sd[nmax + 5];

vector<pair<int,int>> lv[nmax + 5];

Node *Merge(Node *st, Node *dr)
{
    if(st == &nil)
    {
        return dr;
    }
    if(dr == &nil)
    {
        return st;
    }
    if(dr -> val > st -> val)
    {
        swap(st, dr);
    }
    st -> dr = Merge(st -> dr, dr);
    if(st -> st -> len < st -> dr -> len)
    {
        swap(st -> st, st -> dr);
    }
    st -> len = 1 + st -> dr -> len;
    return st;
}

Node *red(Node *it, int val, int nod, int mul)
{
    int cnt = 0;
    while(k - ((it -> val) - lvl[nod]) < val)
    {
        cnt += (it -> cnt);
        rez[nod] += 1LL * (it -> cnt) * mul;
        it = Merge(it -> st, it -> dr);
    }
    if(!cnt)
    {
        return it;
    }
    return Merge(it, new Node{&nil, &nil, lvl[nod], cnt, 1});
}

vector<pair<int,int>> lst;

void parcurg(Node *nod)
{
    lst.push_back({nod -> val, nod -> cnt});
    if(nod -> st != &nil)
    {
        parcurg(nod -> st);
    }
    if(nod -> dr != &nil)
    {
        parcurg(nod -> dr);
    }
}

void get_w(int nod, int dad = 0)
{
    w[nod] = 1;
    for(auto it : G[nod])
    {
        if(it.first == dad || sel[it.first])
        {
            continue;
        }
        get_w(it.first, nod);
        w[nod] += w[it.first];
    }
}

int get_centroid(int nod, int dad = 0)
{
    int Max = sz - w[nod];
    for(auto it : G[nod])
    {
        if(it.first == dad || sel[it.first])
        {
            continue;
        }
        Max = max(Max, w[it.first]);
        int centroid = get_centroid(it.first, nod);
        if(centroid)
        {
            return centroid;
        }
    }
    if(Max <= sz / 2)
    {
        return nod;
    }
    return 0;
}

void dfs(int nod, int dad = 0, int mul = -1)
{
    sd[nod] = new Node{&nil, &nil, lvl[nod], 1, 1};
    for(auto it : G[nod])
    {
        if(it.first == dad || sel[it.first])
        {
            continue;
        }
        lvl[it.first] = lvl[nod] + it.second;
        if(mul == -1)
        {
            dfs(it.first, nod, sz - w[it.first]);
            sd[it.first] = red(sd[it.first], it.second, it.first, sz - w[it.first]);
            lst.clear();
            parcurg(sd[it.first]);
            lv[it.first] = lst;
        }
        else
        {
            dfs(it.first, nod, mul);
            sd[it.first] = red(sd[it.first], it.second, it.first, mul);
        }
        sd[nod] = Merge(sd[nod], sd[it.first]);
    }
}

void debug()
{
    for(auto it=s.begin();it!=s.end();it++)
    {
        cerr<<it->first<<' '<<it->second<<'\n';
    }
    cerr<<'\n';
}

void calc(int nod, int dif, int edge, int dad)
{
    vector<pair<int,int>> rem;
    int cnt = 0;
    while(!s.empty())
    {
        auto it = s.begin();
        if(it -> first >= dif)
        {
            break;
        }
        cnt += it -> second;
        rem.push_back(*it);
        s.erase(it);
    }
    if(cnt)
    {
        s.insert({k + dif - edge, cnt});
    }
    rez[dad] += 1LL * cnt * w[nod];
    for(auto it : G[nod])
    {
        if(it.first == dad || sel[it.first])
        {
            continue;
        }
        calc(it.first, dif + it.second, it.second, nod);
    }
    for(auto it : rem)
    {
        s.insert(it);
    }
    if(cnt)
    {
        auto er = s.lower_bound({k + dif - edge, cnt});
        s.erase(er);
    }
}

void solve(int nod)
{
    get_w(nod);
    sz = w[nod];
    int centroid = get_centroid(nod);
    get_w(centroid);
    sel[centroid] = true;
    lvl[centroid] = 0;
    dfs(centroid);
    lst.clear();
    s.clear();
    parcurg(sd[centroid]);
    for(auto it : lst)
    {
        s.insert({k - it.first, it.second});
    }
    for(auto son : G[centroid])
    {
        if(sel[son.first])
        {
            continue;
        }
        for(auto it : lv[son.first])
        {
            auto er = s.lower_bound({k - it.first, it.second});
            s.erase(er);
        }
        calc(son.first, son.second, son.second, centroid);
        for(auto it : lv[son.first])
        {
            s.insert({k - it.first, it.second});
        }
    }
    for(auto it : G[centroid])
    {
        if(sel[it.first])
        {
            continue;
        }
        solve(it.first);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>k;
    for(int i=1; i<n; i++)
    {
        int x, y, c;
        cin>>x>>y>>c;
        ++x;
        ++y;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }
    solve(1);
    for(int i=1;i<=n;i++)
    {
        cout<<rez[i]<<'\n';
    }
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 18 / 18
• Subtask 2: 8 / 8
• Subtask 3: 10 / 10
• Subtask 4: 12 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35