Submission #1232132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232132		PVM_pvm	Petrol stations (CEOI24_stations)	C++20	18 / 100	3592 ms	11960 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define MAXN 70'007
long long otg[MAXN];
int n,k;
long long st[MAXN],fen[MAXN];
void Update(int x, long long ch)
{
    while (x<=n)
    {
        fen[x]+=ch;
        x+=x&(-x);
    }
}
long long Query(int x)
{
    long long ans=0;
    while (x>0)
    {
        ans+=fen[x];
        x-=x&(-x);
    }
    return ans;
}
vector<pair<int,int>> v[MAXN];
vector<int> nm;
vector<long long> dst;
void dfs(int x, int par, long long dd)
{
    nm.push_back(x);
    dst.push_back(dd);
    for (int q=0;q<v[x].size();q++)
    {
        if (v[x][q].first==par) continue;
        dfs(v[x][q].first,x,dd+v[x][q].second);
    }
}
void solvefrom(int root)
{
    nm.clear();
    dst.clear();
    dfs(root,-1,0);
    for (int q=0;q<=n;q++) st[q]=0;
    for (int q=0;q<=n;q++) fen[q]=0;
    st[n-1]=n-1;
    Update(n,1);
    for (int q=n-2;q>0;q--)
    {
        long long reb=dst[q]-dst[q-1];
        int l=q,r=n;
        while (l<r-1)
        {
            int mid=(l+r)/2;
            long long raz=dst[mid]-dst[q];
            if (raz<=k) l=mid;
            else r=mid;
        }
        int desen=l;
        l=q;
        r=n;
        while (l<r-1)
        {
            int mid=(l+r)/2;
            long long raz=dst[mid]-dst[q];
            if (raz<=(k-reb)) l=mid;
            else r=mid;
        }
        //cout<<q<<" "<<l<<" "<<desen<<"\n";
        if (desen==q)
        {
            st[q]=q;
        }
        else
        {
            st[q]=q+1LL*q*(Query(desen+1)-Query(l+1));
        }
        //cout<<q<<" "<<st[q]<<"\n";
        Update(q+1,st[q]/q);
    }
    for (int q=0;q<n;q++) otg[ nm[q] ]+=st[q];
}
int main()
{
    cin>>n>>k;
    for (int q=0;q<n-1;q++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    for (int q=0;q<n;q++)
    {
        if (v[q].size()==1)
        {
            solvefrom(q);
        }
    }
    for (int q=0;q<n;q++) cout<<otg[q]-n+1<<"\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 18
• Subtask 2: 8 / 8
• Subtask 3: 10 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35