제출 #1221097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221097		KindaGoodGames	Petrol stations (CEOI24_stations)	C++20	0 / 100	95 ms	6468 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;
    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); 
            }else{
                ans[par] += (n-steps-1);  
            }
            pq.pop();
        }

        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