oj.uz

Submission #1039679

# Submission time Handle Problem Language Result Execution time Memory
1039679 2024-07-31T07:30:05 Z 정희우(#10993) Petrol stations (CEOI24_stations) C++17
100 / 100
 1004 ms 208584 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;
using vlint = vector<lint>;
using lntp = pair<lint,lint>;
using pqpll = priority_queue<lntp>;

const int MAX_N=70010;

struct Edge
{
    int v;
    lint d;
};

int n;
lint k;
vector<Edge> edge[MAX_N];
int sz[MAX_N];
int lock[MAX_N];
lint ans[MAX_N];

int fillsz(int v,int p)
{
    sz[v]=1;
    for(auto e : edge[v])
        if(e.v!=p && lock[e.v]==0)
            sz[v]+=fillsz(e.v,v);
    return sz[v];
}

int findc(int v,int p,int h)
{
    for(auto e : edge[v])
        if(e.v!=p && lock[e.v]==0 && sz[e.v]>h)
            return findc(e.v,v,h);
    return v;
}

struct Cent
{
    int pn;
    vlint px;
    vlint seg;
    vector<Edge> sube;
    vector<vector<lntp>> sub;
    void init_()
    {
        sort(px.begin(),px.end());
        pn=unique(px.begin(),px.end())-px.begin()-1;
        px.resize(pn+1);
        seg.resize(pn<<2);
    }
    int fp(lint x)
    {
        return lower_bound(px.begin(),px.end(),x)-px.begin();
    }
    void update_(int i,int s,int e,int x,lint v)
    {
        if(s>x || e<=x)return;
        if(s==x && x+1==e)
        {
            seg[i]+=v;
            return;
        }
        update_(i<<1,s,(s+e)>>1,x,v);
        update_(i<<1|1,(s+e)>>1,e,x,v);
        seg[i]=seg[i<<1]+seg[i<<1|1];
    }
    lint find_(int i,int s,int e,int l,int r)
    {
        if(s>=r || e<=l)return 0;
        if(l<=s && e<=r)return seg[i];
        return find_(i<<1,s,(s+e)>>1,l,r)+find_(i<<1|1,(s+e)>>1,e,l,r);
    }
    void filld(int v,int p,lint ds,lint d)
    {
        if(ds<=k)px.push_back(-ds);
        px.push_back(ds-d-k);
        px.push_back(ds-k);
        px.push_back(ds-d);
        for(auto e : edge[v])
            if(e.v!=p && lock[e.v]==0)
                filld(e.v,v,ds+e.d,e.d);
    }
    pqpll* calcup(int v,int p,lint ds,lint d,int usz)
    {
        pqpll *pq=NULL,*comp=NULL;
        for(auto e : edge[v])
            if(e.v!=p && lock[e.v]==0)
            {
                comp=calcup(e.v,v,ds+e.d,e.d,usz);
                if(pq==NULL || pq->size()<comp->size())swap(pq,comp);
                while(comp!=NULL && !comp->empty())
                {
                    pq->push(comp->top());
                    comp->pop();
                }
                if(comp!=NULL)
                    free(comp);
            }
        if(pq==NULL)pq=new pqpll;
        lint cnt=0;
        while(!pq->empty() && pq->top().first>ds-d+k)
        {
            cnt+=pq->top().second;
            pq->pop();
        }
        ans[v]+=cnt*usz;
        pq->push({ds,cnt+1});
        return pq;
    }
    void calcdown(int v,int p,lint ds,lint d)
    {
        lint s=find_(1,0,pn,fp(ds-d-k),fp(ds-k));
        ans[p]+=s*sz[v];
        update_(1,0,pn,fp(ds-d),s);
        for(auto e : edge[v])
            if(e.v!=p && lock[e.v]==0)
                calcdown(e.v,v,ds+e.d,e.d);
        update_(1,0,pn,fp(ds-d),-s);
    }
    void calc(int v)
    {
        fillsz(v,v);
        filld(v,v,0,0);
        init_();
        for(auto e : edge[v])
            if(lock[e.v]==0)
            {
                sube.push_back(e);
                pqpll *pq=calcup(e.v,v,e.d,e.d,sz[v]-sz[e.v]);
                sub.push_back({});
                while(!pq->empty())
                {
                    sub.back().push_back(pq->top());
                    pq->pop();
                }
                free(pq);
                for(auto p : sub.back())
                    update_(1,0,pn,fp(-p.first),p.second);
            }
        update_(1,0,pn,fp(0),1);
        for(int i=0;i<sube.size();i++)
        {
            auto e=sube[i];
            for(auto p : sub[i])
                update_(1,0,pn,fp(-p.first),-p.second);
            calcdown(e.v,v,e.d,e.d);
            for(auto p : sub[i])
                update_(1,0,pn,fp(-p.first),p.second);
        }
    }
};

Cent cent[MAX_N];

void f(int v)
{
    fillsz(v,v);
    v=findc(v,v,sz[v]/2);
    cent[v].calc(v);
    lock[v]=1;
    for(auto e : edge[v])
        if(lock[e.v]==0)
            f(e.v);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> k;
    for(int i=1;i<n;i++)
    {
        int u,v;
        lint d;
        cin >> u >> v >> d;
        edge[u].push_back({v,d});
        edge[v].push_back({u,d});
    }
    f(0);
    for(int i=0;i<n;i++)
        cout << ans[i] << '\n';
    return 0;
}

Compilation message

Main.cpp: In member function 'void Cent::calc(int)':
Main.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for(int i=0;i<sube.size();i++)
      |                     ~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10076 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Correct 7 ms 11100 KB Output is correct
4 Correct 8 ms 11356 KB Output is correct
5 Correct 6 ms 10844 KB Output is correct
6 Correct 8 ms 11356 KB Output is correct
7 Correct 6 ms 10936 KB Output is correct
8 Correct 3 ms 10076 KB Output is correct
9 Correct 7 ms 9820 KB Output is correct
10 Correct 7 ms 9820 KB Output is correct
11 Correct 10 ms 11004 KB Output is correct
12 Correct 7 ms 11100 KB Output is correct
13 Correct 7 ms 11004 KB Output is correct
14 Correct 5 ms 10584 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 600 ms 76848 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10076 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 600 ms 76848 KB Output is correct
5 Correct 788 ms 132064 KB Output is correct
6 Correct 1004 ms 208584 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10076 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Correct 457 ms 72640 KB Output is correct
4 Correct 706 ms 91512 KB Output is correct
5 Correct 382 ms 119992 KB Output is correct
6 Correct 4 ms 10076 KB Output is correct
7 Correct 512 ms 78912 KB Output is correct
8 Correct 539 ms 80276 KB Output is correct
9 Correct 546 ms 79048 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10076 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Correct 457 ms 72640 KB Output is correct
4 Correct 706 ms 91512 KB Output is correct
5 Correct 382 ms 119992 KB Output is correct
6 Correct 4 ms 10076 KB Output is correct
7 Correct 512 ms 78912 KB Output is correct
8 Correct 539 ms 80276 KB Output is correct
9 Correct 546 ms 79048 KB Output is correct
10 Correct 305 ms 56124 KB Output is correct
11 Correct 359 ms 67356 KB Output is correct
12 Correct 318 ms 68292 KB Output is correct
13 Correct 372 ms 69832 KB Output is correct
14 Correct 353 ms 68596 KB Output is correct
15 Correct 334 ms 69384 KB Output is correct
16 Correct 68 ms 30520 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10076 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Correct 7 ms 11100 KB Output is correct
4 Correct 8 ms 11356 KB Output is correct
5 Correct 6 ms 10844 KB Output is correct
6 Correct 8 ms 11356 KB Output is correct
7 Correct 6 ms 10936 KB Output is correct
8 Correct 3 ms 10076 KB Output is correct
9 Correct 7 ms 9820 KB Output is correct
10 Correct 7 ms 9820 KB Output is correct
11 Correct 10 ms 11004 KB Output is correct
12 Correct 7 ms 11100 KB Output is correct
13 Correct 7 ms 11004 KB Output is correct
14 Correct 5 ms 10584 KB Output is correct
15 Correct 3 ms 9052 KB Output is correct
16 Correct 600 ms 76848 KB Output is correct
17 Correct 788 ms 132064 KB Output is correct
18 Correct 1004 ms 208584 KB Output is correct
19 Correct 457 ms 72640 KB Output is correct
20 Correct 706 ms 91512 KB Output is correct
21 Correct 382 ms 119992 KB Output is correct
22 Correct 4 ms 10076 KB Output is correct
23 Correct 512 ms 78912 KB Output is correct
24 Correct 539 ms 80276 KB Output is correct
25 Correct 546 ms 79048 KB Output is correct
26 Correct 305 ms 56124 KB Output is correct
27 Correct 359 ms 67356 KB Output is correct
28 Correct 318 ms 68292 KB Output is correct
29 Correct 372 ms 69832 KB Output is correct
30 Correct 353 ms 68596 KB Output is correct
31 Correct 334 ms 69384 KB Output is correct
32 Correct 68 ms 30520 KB Output is correct
33 Correct 912 ms 169076 KB Output is correct
34 Correct 391 ms 70084 KB Output is correct
35 Correct 511 ms 92456 KB Output is correct
36 Correct 523 ms 91612 KB Output is correct
37 Correct 723 ms 137064 KB Output is correct
38 Correct 738 ms 140480 KB Output is correct
39 Correct 711 ms 140736 KB Output is correct
40 Correct 157 ms 35384 KB Output is correct