Submission #1221130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221130		KindaGoodGames	Petrol stations (CEOI24_stations)	C++20	0 / 100	106 ms	6924 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

vector<vector<pii>> adj;
int n, k;
vector<int>ans;

void DFS(int s){ 
    int node = s;
    int par = -1;

    priority_queue<int, vector<int>, greater<int>> pq;
    map<int, int> m2;
    int cur = 0;
    int steps = 1;
    while(true){
        while(pq.size() && (cur-pq.top()) >= k && adj[node].size() >= 2){
            if((cur-pq.top()) == k){
                ans[node] += (n-steps); 
                m2[cur]++;
            }else{
                ans[par] += (n-steps-1);  
                m2[cur]++;
            }
            pq.pop();
        }
        while(true){
            if(m2.empty()) break;
            pii it = *m2.begin();
            if((cur-it.first) < k) break;
            int v = (*m2.begin()).first;
            m2.erase(v);
            if((cur-v) == k && adj[node].size() >= 2){
                ans[node] += (n-steps)*it.second; 
                m2[cur] += it.second;
            }else{
                ans[par] += (n-steps-1)*it.second;  
                m2[cur] += it.second;
            } 
        }

        steps++;
        pq.push(cur);
        if(adj[node][0].first != par){
            par = node;
            cur +=adj[node][0].second;
            node=adj[node][0].first;
        }else if(adj[node].size() >= 2){ 
            par = node;
            cur +=adj[node][1].second;
            node=adj[node][1].first;
        }else{
            break;
        }
    }
} 

int32_t main(){
    cin >> n >> k; 

    adj.resize(n); 
    ans.resize(n); 

    for(int i = 0; i < n-1; i++){
        int a,b,c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    
    for(int i = 0; i < n; i++){
        if(adj[i].size() == 1){
            DFS(i);
        }
    }

    for(int i = 0; i < n; i++){
        cout << ans[i] << endl;
    }
}

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