oj.uz

답안 #1039670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039670 2024-07-31T07:21:29 Z 정희우(#10993) Petrol stations (CEOI24_stations) C++17
0 / 100
 618 ms 77772 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 tsz;
    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)
    {
        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);
                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*(tsz-sz[v]);
        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_();
        tsz=sz[v];
        for(auto e : edge[v])
            if(lock[e.v]==0)
            {
                sube.push_back(e);
                pqpll *pq=calcup(e.v,v,e.d,e.d);
                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);
            }
        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:151:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for(int i=0;i<sube.size();i++)
      |                     ~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Incorrect 4 ms 10076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Incorrect 4 ms 10076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10076 KB Output is correct
2 Incorrect 618 ms 77772 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Incorrect 4 ms 10076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Incorrect 4 ms 10076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Incorrect 4 ms 10076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Incorrect 4 ms 10076 KB Output isn't correct
3 Halted 0 ms 0 KB -