제출 #1364975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364975		Sofiatpc	Petrol stations (CEOI24_stations)	C++20	18 / 100	41 ms	23136 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define sc second
#define sz(v) (int)v.size()
const int MAXN = 7*1e4+5;
vector< pair<int,int > > adj[MAXN];
vector<int> dir[2][MAXN];
int viz[2][MAXN], w[2][MAXN], pos[MAXN], sub[2][MAXN], lst, k;

void dfsIni(int s, int p){
    lst = s;
    for(auto [v,peso] : adj[s])
        if(v != p){
            viz[0][s] = v; w[0][s] = peso;
            viz[1][v] = s; w[1][v] = peso;
            pos[v] = pos[s]+1;
            dfsIni(v, s);
        }
}

void faz(int x, int ini){
    int a = ini, b = ini, sum = 0;
    while(a != -1){
        while(viz[x][b] != -1 && sum + w[x][b] <= k ){
            sum += w[x][b];
            b = viz[x][b];
        }

        if(viz[x][b] == -1)break;
        dir[x][b].push_back(a);

        sum -= w[x][a];
        a = viz[x][a];
    }
}

void dfs(int x, int s, int p){
    sub[x][s] = 1;
    for(int v : dir[x][s])
        if(v != p){
            dfs(x,v,s);
            sub[x][s] += sub[x][v];
        }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin>>n>>k;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < 2; j++)viz[j][i] = -1;

    for(int i = 1; i < n; i++){
        int a,b,c; cin>>a>>b>>c;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }

    int ini;
    for(int i = 0; i < n; i++)
        if(sz(adj[i]) == 1)ini = i;
    
    dfsIni(ini,-1);

    faz(0,ini); faz(1, lst);

    int cur = lst;
    while(cur != -1){
        if(!sub[0][cur])dfs(0,cur,-1);
        cur = viz[1][cur];
    }
    
    cur = ini;
    while(cur != -1){
        if(!sub[1][cur])dfs(1,cur,-1);
        cur = viz[0][cur];
    }

    for(int i = 0; i < n; i++)cout<<pos[i]*(sub[1][i]-1) + (n-pos[i]-1)*(sub[0][i]-1)<<"\n";
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 0 / 18
• 서브태스크 2: 8 / 8
• 서브태스크 3: 10 / 10
• 서브태스크 4: 0 / 12
• 서브태스크 5: 0 / 17
• 서브태스크 6: 0 / 35