oj.uz

Submission #1118534

# Submission time Handle Problem Language Result Execution time Memory
1118534 2024-11-25T16:12:21 Z Tenis0206 Petrol stations (CEOI24_stations) C++11
48 / 100
 3500 ms 110892 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3672 KB Output is correct
2 Correct 4 ms 3856 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3672 KB Output is correct
2 Correct 4 ms 3856 KB Output is correct
3 Correct 10 ms 4108 KB Output is correct
4 Correct 7 ms 4344 KB Output is correct
5 Correct 16 ms 4200 KB Output is correct
6 Correct 6 ms 4556 KB Output is correct
7 Correct 5 ms 4444 KB Output is correct
8 Correct 3 ms 3676 KB Output is correct
9 Correct 6 ms 4188 KB Output is correct
10 Correct 5 ms 4188 KB Output is correct
11 Correct 7 ms 4040 KB Output is correct
12 Correct 6 ms 4040 KB Output is correct
13 Correct 7 ms 4188 KB Output is correct
14 Correct 95 ms 4088 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3676 KB Output is correct
2 Correct 568 ms 110892 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3672 KB Output is correct
2 Correct 4 ms 3856 KB Output is correct
3 Correct 5 ms 3676 KB Output is correct
4 Correct 568 ms 110892 KB Output is correct
5 Correct 564 ms 95900 KB Output is correct
6 Correct 722 ms 84076 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3672 KB Output is correct
2 Correct 4 ms 3856 KB Output is correct
3 Correct 535 ms 83268 KB Output is correct
4 Correct 495 ms 92232 KB Output is correct
5 Correct 544 ms 82152 KB Output is correct
6 Correct 4 ms 3664 KB Output is correct
7 Correct 452 ms 65352 KB Output is correct
8 Correct 432 ms 67160 KB Output is correct
9 Correct 420 ms 65820 KB Output is correct

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3672 KB Output is correct
2 Correct 4 ms 3856 KB Output is correct
3 Correct 535 ms 83268 KB Output is correct
4 Correct 495 ms 92232 KB Output is correct
5 Correct 544 ms 82152 KB Output is correct
6 Correct 4 ms 3664 KB Output is correct
7 Correct 452 ms 65352 KB Output is correct
8 Correct 432 ms 67160 KB Output is correct
9 Correct 420 ms 65820 KB Output is correct
10 Execution timed out 3515 ms 20232 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3672 KB Output is correct
2 Correct 4 ms 3856 KB Output is correct
3 Correct 10 ms 4108 KB Output is correct
4 Correct 7 ms 4344 KB Output is correct
5 Correct 16 ms 4200 KB Output is correct
6 Correct 6 ms 4556 KB Output is correct
7 Correct 5 ms 4444 KB Output is correct
8 Correct 3 ms 3676 KB Output is correct
9 Correct 6 ms 4188 KB Output is correct
10 Correct 5 ms 4188 KB Output is correct
11 Correct 7 ms 4040 KB Output is correct
12 Correct 6 ms 4040 KB Output is correct
13 Correct 7 ms 4188 KB Output is correct
14 Correct 95 ms 4088 KB Output is correct
15 Correct 5 ms 3676 KB Output is correct
16 Correct 568 ms 110892 KB Output is correct
17 Correct 564 ms 95900 KB Output is correct
18 Correct 722 ms 84076 KB Output is correct
19 Correct 535 ms 83268 KB Output is correct
20 Correct 495 ms 92232 KB Output is correct
21 Correct 544 ms 82152 KB Output is correct
22 Correct 4 ms 3664 KB Output is correct
23 Correct 452 ms 65352 KB Output is correct
24 Correct 432 ms 67160 KB Output is correct
25 Correct 420 ms 65820 KB Output is correct
26 Execution timed out 3515 ms 20232 KB Time limit exceeded
27 Halted 0 ms 0 KB -