Submission #1045952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045952		gagik_2007	Petrol stations (CEOI24_stations)	C++17	36 / 100	86 ms	10132 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=70007;
ll n,m,k;
int sz[N];
vector<pair<int,ll>>g[N];
ll ans[N];

void calcsz(int v, int par){
    sz[v]=1;
    for(auto e:g[v]){
        int to=e.ff;
        if(to!=par){
            calcsz(to,v);
            sz[v]+=sz[to];
        }
    }
}

void dfs(int v, int par, ll cur){
    // cout<<"TAZA DFS"<<endl;
    for(auto e:g[v]){
        int to=e.ff;
        ll w=e.ss;
        // cout<<"dfs: "<<v<<" "<<par<<" "<<cur<<endl;
        // cout<<"edge: "<<to<<" "<<w<<endl;
        if(to!=par){
            if(cur+w>k){
                // cout<<to<<" "<<cur<<endl;
                ans[v]+=sz[to];
                dfs(to,v,w);
            }
            else{
                dfs(to,v,cur+w);
            }
        }
    }
}

ll getdist(const vector<ll>& pf, int x, int y){
    if(x==0)return pf[y-1];
    return pf[y-1]-pf[x-1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("Einput.txt","r",stdin);
    // freopen("Eoutput.txt","w",stdout);
    cin>>n>>k;
    for(int i=0;i<n-1;i++){
        int u,v;
        ll w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    if(n<=1000){
        for(int v=0;v<n;v++){
            // cout<<"root: "<<v<<endl;
            calcsz(v,-1);
            dfs(v,-1,0);
        }
        for(int v=0;v<n;v++){
            cout<<ans[v]<<endl;
        }
    }
    else{
        vector<int>a;
        vector<ll>p;
        int root=0;
        for(int v=0;v<n;v++){
            if(g[v].size()==1){
                root=v;
                break;
            }
        }
        a.push_back(root);
        a.push_back(g[root][0].ff);
        p.push_back(g[root][0].ss);
        root=g[root][0].ff;
        while(g[root].size()!=1){
            if(g[root][0].ff!=a[a.size()-2]){
                a.push_back(g[root][0].ff);
                p.push_back(g[root][0].ss);
                root=g[root][0].ff;
            }
            else{
                a.push_back(g[root][1].ff);
                p.push_back(g[root][1].ss);
                root=g[root][1].ff;
            }
        }
        vector<int>prev(a.size(),-1);
        int l=a.size()-1;
        ll sum=0;
        for(int r=a.size()-1;r>=0;r--){
            while(l>0&&sum<=k){
                l--;
                sum+=p[l];
            }
            if(sum>k)prev[r]=l+1;
            sum-=p[r-1];
        }
        vector<int>nxt(a.size(),a.size());
        l=0;
        sum=0;
        for(int r=0;r<a.size();r++){
            while(l<a.size()-1&&sum<=k){
                sum+=p[l];
                l++;
            }
            if(sum>k)nxt[r]=l-1;
            sum-=p[r];
        }
        vector<ll>ansnxt(a.size(),0);
        for(int i=0;i<a.size();i++){
            if(nxt[i]!=a.size()){
                ansnxt[nxt[i]]+=ansnxt[i]+1;
            }
            ansnxt[i]*=(a.size()-i-1);
            ans[a[i]]+=ansnxt[i];
        }
        vector<ll>ansprev(a.size(),0);
        for(int i=a.size()-1;i>=0;i--){
            if(prev[i]!=-1){
                ansprev[prev[i]]+=ansprev[i]+1;
            }
            ansprev[i]*=i;
            ans[a[i]]+=ansprev[i];
        }
        // for(int i=0;i<a.size();i++){
        //     cout<<i<<": "<<a[i]<<" "<<nxt[i]<<" "<<prev[i]<<" "<<ansnxt[i]<<" "<<ansprev[i]<<endl;
        // }
        for(int i=0;i<n;i++){
            cout<<ans[i]<<endl;
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int r=0;r<a.size();r++){
      |                     ~^~~~~~~~~
Main.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             while(l<a.size()-1&&sum<=k){
      |                   ~^~~~~~~~~~~
Main.cpp:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for(int i=0;i<a.size();i++){
      |                     ~^~~~~~~~~
Main.cpp:131:22: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |             if(nxt[i]!=a.size()){

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