oj.uz

Submission #1045952

# Submission time Handle Problem Language Result Execution time Memory
1045952 2024-08-06T08:42:23 Z gagik_2007 Petrol stations (CEOI24_stations) C++17
36 / 100
 86 ms 10132 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 9 ms 2392 KB Output is correct
4 Correct 16 ms 2592 KB Output is correct
5 Correct 10 ms 2392 KB Output is correct
6 Correct 22 ms 2532 KB Output is correct
7 Correct 19 ms 2652 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 15 ms 2392 KB Output is correct
10 Correct 11 ms 2396 KB Output is correct
11 Correct 11 ms 2396 KB Output is correct
12 Correct 11 ms 2592 KB Output is correct
13 Correct 11 ms 2396 KB Output is correct
14 Correct 9 ms 2396 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 82 ms 10132 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 82 ms 10132 KB Output is correct
5 Correct 86 ms 9404 KB Output is correct
6 Correct 86 ms 9152 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 72 ms 6992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 72 ms 6992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 9 ms 2392 KB Output is correct
4 Correct 16 ms 2592 KB Output is correct
5 Correct 10 ms 2392 KB Output is correct
6 Correct 22 ms 2532 KB Output is correct
7 Correct 19 ms 2652 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 15 ms 2392 KB Output is correct
10 Correct 11 ms 2396 KB Output is correct
11 Correct 11 ms 2396 KB Output is correct
12 Correct 11 ms 2592 KB Output is correct
13 Correct 11 ms 2396 KB Output is correct
14 Correct 9 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 82 ms 10132 KB Output is correct
17 Correct 86 ms 9404 KB Output is correct
18 Correct 86 ms 9152 KB Output is correct
19 Incorrect 72 ms 6992 KB Output isn't correct
20 Halted 0 ms 0 KB -