제출 #1118568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118568		Tenis0206	Petrol stations (CEOI24_stations)	C++11	38 / 100	3529 ms	27284 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nmax = 70000;

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

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

multiset<pair<long long,int>> s;

long long rez[nmax + 5];

priority_queue<pair<int,int>> *sd[nmax + 5];

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

vector<pair<int,int>> lst;

void parcurg(priority_queue<pair<int,int>> *h, bool del = false)
{
    while(!h->empty())
    {
        lst.push_back(h->top());
        h->pop();
    }
    if(!del)
    {
        for(auto it : lst)
        {
            h->push(it);
        }
    }
}

priority_queue<pair<int,int>> *red(priority_queue<pair<int,int>> *h, int val, int nod, int mul)
{
    int cnt = 0;
    while(!h->empty() && k - ((h -> top().first) - lvl[nod]) < val)
    {
        cnt += (h -> top().second);
        rez[nod] += 1LL * (h -> top().second) * mul;
        h->pop();
    }
    if(!cnt)
    {
        return h;
    }
    h->push({lvl[nod], cnt});
    return h;
}

void get_w(int nod, int dad = 0)
{
    w[nod] = 1;
    Max[nod] = 0;
    for(auto it : G[nod])
    {
        if(it.first == dad || sel[it.first])
        {
            continue;
        }
        get_w(it.first, nod);
        if(w[it.first] > w[Max[nod]])
        {
            Max[nod] = it.first;
            eMax[nod] = it.second;
        }
        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 debug(vector<pair<int,int>> c)
{
    for(auto it : c)
    {
        cerr<<it.first<<' '<<it.second<<'\n';
    }
    cerr<<'\n';
}

void dfs(int nod, int dad = 0, int mul = -1, int path = 1)
{
    if(Max[nod] == 0)
    {
        sd[path] -> push({lvl[nod], 1});
        return;
    }
    lvl[Max[nod]] = lvl[nod] + eMax[nod];
    if(mul == -1)
    {
        dfs(Max[nod], nod, sz - w[Max[nod]], path);
        sd[path] = red(sd[path], eMax[nod], Max[nod], sz - w[Max[nod]]);
        lst.clear();
        parcurg(sd[path]);
        lv[Max[nod]] = lst;
    }
    else
    {
        dfs(Max[nod], nod, mul, path);
        sd[path] = red(sd[path], eMax[nod], Max[nod], mul);
    }
    sd[path] -> push({lvl[nod], 1});
    for(auto it : G[nod])
    {
        if(it.first == dad || sel[it.first] || it.first == Max[nod])
        {
            continue;
        }
        lvl[it.first] = lvl[nod] + it.second;
        if(mul == -1)
        {
            dfs(it.first, nod, sz - w[it.first], path + 1);
            sd[path + 1] = red(sd[path + 1], it.second, it.first, sz - w[it.first]);
            lst.clear();
            parcurg(sd[path + 1], true);
            lv[it.first] = lst;
        }
        else
        {
            dfs(it.first, nod, mul, path + 1);
            sd[path + 1] = red(sd[path + 1], it.second, it.first, mul);
            lst.clear();
            parcurg(sd[path + 1], true);
        }
        for(auto er : lst)
        {
            sd[path] -> push(er);
        }
    }
}

void calc(int nod, long long dif, int edge, int dad)
{
    vector<pair<long long,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[1], true);
    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);
    }
}

int 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++)
    {
        sd[i] = new priority_queue<pair<int,int>>();
    }
    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: 0 / 10
• Subtask 4: 12 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35