제출 #1289674

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

Main

// Author: Štěpán Mikéska
#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

constexpr int N = 70000;

struct E {
    int v;
    int l;
};

int n, k;
bool block[N];
int sts[N];
vector<E> sl[N];
ll pets[N];

void get_sts(int u, int p) {
    sts[u] = 1;
    for(auto[a, l] : sl[u]) {
        if(a == p) continue;
        if(block[a]) continue;
        get_sts(a, u);
        sts[u] += sts[a];
    }
}

int cen_walk(int u) {
    for(auto[a, l] : sl[u]) {
        if(sts[a]*2 > sts[u]) {
            sts[u] -= sts[a];
            sts[a] += sts[u];
            return cen_walk(a);
        }
    }

    return u;
}

int rotbuf[2000];

int rot(vector<int>& vec, int l) {
    for(int i = 0; i <= k; ++i) {
        rotbuf[i] = 0;
    }
    return 3;
}

vector<int> upwalk(int u) {}
void downwalk(int u, vector<int> ps) {}

void cen_dec(int u) {
    if(block[u]) return;
    get_sts(u, -1);
    u = cen_walk(u);
    if(sts[u] == 1) return;

    int chc = sl[u].size();
    vector<vector<int>> chs(chc);
    for(int i = 0; i < chc; ++i) {
        auto[a, l] = sl[u][i];
        chs[i] = upwalk(a);
    }
    vector<int> al(k+1);
    al[k] = 1;
    for(int i = 0; i < chc; ++i) {
        for(int j = 0; j <= k; ++j) {
            al[j] += chs[i][j];
        }
    }
    for(int i = 0; i < chc; ++i) {
        auto[a, l] = sl[u][i];
        for(int j = 0; j <= k; ++j) {
            al[j] -= chs[i][j];
        }
        downwalk(a, al);
        for(int j = 0; j <= k; ++j) {
            al[j] += chs[i][j];
        }
    }

    block[u] = true;
    for(int i = 0; i < chc; ++i) {
        auto[a, l] = sl[u][i];
        cen_walk(a);
    }
    return;
}

void bwalk(int v, int p, int t) {
    for(auto[a, l] : sl[v]) {
        if(a == p) continue;
        if(l > t) {
            pets[v] += sts[a];
            bwalk(a, v, k-l);
        } else {
            bwalk(a, v, t-l);
        }
    }
}

void solve() {
    cin >> n >> k;

    for(int i = 0; i < n-1; ++i) {
        int u, v, l;
        cin >> u >> v >> l;
        sl[u].push_back({v, l});
        sl[v].push_back({u, l});
    }
    if(n < 2000) {
        for(int i = 0; i < n; ++i) {
            get_sts(i, -1);
            bwalk(i, -1, k);
        }
    } else {
        if(k > 2000) return;
        cen_dec(0);
    }
    for(int i = 0; i < n; ++i) {
        cout << pets[i] << '\n';
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(20);

    solve();
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'std::vector<int> upwalk(int)':
Main.cpp:63:28: warning: no return statement in function returning non-void [-Wreturn-type]
   63 | vector<int> upwalk(int u) {}
      |                            ^

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