oj.uz

Submission #1118543

# Submission time Handle Problem Language Result Execution time Memory
1118543 2024-11-25T16:20:41 Z Tenis0206 Petrol stations (CEOI24_stations) C++11
48 / 100
 3500 ms 109908 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(true)
    {
        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 3676 KB Output is correct
2 Correct 4 ms 3680 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3676 KB Output is correct
2 Correct 4 ms 3680 KB Output is correct
3 Correct 7 ms 3932 KB Output is correct
4 Correct 8 ms 4188 KB Output is correct
5 Correct 15 ms 4188 KB Output is correct
6 Correct 7 ms 4608 KB Output is correct
7 Correct 7 ms 4296 KB Output is correct
8 Correct 3 ms 3676 KB Output is correct
9 Correct 5 ms 4188 KB Output is correct
10 Correct 8 ms 4188 KB Output is correct
11 Correct 5 ms 4216 KB Output is correct
12 Correct 9 ms 4188 KB Output is correct
13 Correct 6 ms 4188 KB Output is correct
14 Correct 115 ms 3932 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3680 KB Output is correct
2 Correct 545 ms 109908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3676 KB Output is correct
2 Correct 4 ms 3680 KB Output is correct
3 Correct 3 ms 3680 KB Output is correct
4 Correct 545 ms 109908 KB Output is correct
5 Correct 495 ms 95736 KB Output is correct
6 Correct 884 ms 84096 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3676 KB Output is correct
2 Correct 4 ms 3680 KB Output is correct
3 Correct 617 ms 83200 KB Output is correct
4 Correct 476 ms 92188 KB Output is correct
5 Correct 553 ms 81280 KB Output is correct
6 Correct 3 ms 3664 KB Output is correct
7 Correct 359 ms 64608 KB Output is correct
8 Correct 381 ms 67144 KB Output is correct
9 Correct 358 ms 65952 KB Output is correct

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3676 KB Output is correct
2 Correct 4 ms 3680 KB Output is correct
3 Correct 617 ms 83200 KB Output is correct
4 Correct 476 ms 92188 KB Output is correct
5 Correct 553 ms 81280 KB Output is correct
6 Correct 3 ms 3664 KB Output is correct
7 Correct 359 ms 64608 KB Output is correct
8 Correct 381 ms 67144 KB Output is correct
9 Correct 358 ms 65952 KB Output is correct
10 Execution timed out 3535 ms 20188 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 3676 KB Output is correct
2 Correct 4 ms 3680 KB Output is correct
3 Correct 7 ms 3932 KB Output is correct
4 Correct 8 ms 4188 KB Output is correct
5 Correct 15 ms 4188 KB Output is correct
6 Correct 7 ms 4608 KB Output is correct
7 Correct 7 ms 4296 KB Output is correct
8 Correct 3 ms 3676 KB Output is correct
9 Correct 5 ms 4188 KB Output is correct
10 Correct 8 ms 4188 KB Output is correct
11 Correct 5 ms 4216 KB Output is correct
12 Correct 9 ms 4188 KB Output is correct
13 Correct 6 ms 4188 KB Output is correct
14 Correct 115 ms 3932 KB Output is correct
15 Correct 3 ms 3680 KB Output is correct
16 Correct 545 ms 109908 KB Output is correct
17 Correct 495 ms 95736 KB Output is correct
18 Correct 884 ms 84096 KB Output is correct
19 Correct 617 ms 83200 KB Output is correct
20 Correct 476 ms 92188 KB Output is correct
21 Correct 553 ms 81280 KB Output is correct
22 Correct 3 ms 3664 KB Output is correct
23 Correct 359 ms 64608 KB Output is correct
24 Correct 381 ms 67144 KB Output is correct
25 Correct 358 ms 65952 KB Output is correct
26 Execution timed out 3535 ms 20188 KB Time limit exceeded
27 Halted 0 ms 0 KB -