제출 #1246698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246698		CodeLakVN	Transport (COCI19_transport)	C++17	0 / 100	0 ms	0 KiB

Main

#include <bits/stdc++.h>

#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define task "DATA"
#define _mp make_pair
#define ll long long
#define ii pair<int, int>
#define li pair<ll, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maximize(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool minimize(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int numNode, sz, ans = 0;
ll a[N];
vector<ii> adj[N];
int child[N], id[N];
bool del[N];
vector<li> costUp;
int bit[N];

void update(int idx, int val) {
    while (idx <= sz) {
        bit[idx] += val;
        idx += (idx & (-idx));
    }
}

int get(int idx) {
    int res = 0;
    while (idx > 0) {
        res += bit[idx];
        idx -= (idx & (-idx));
    }
    return res;
}

int countChild(int u, int p) {
    child[u] = 1;
    for (auto e : adj[u]) {
        int v = e.F;
        if (v == p || del[v]) continue;
        child[u] += countChild(v, u);
    }
    return child[u];
}

int centroid(int u, int p, int m) {
    for (auto e : adj[u]) {
        int v = e.F;
        if (v == p || del[v]) continue;
        if (child[v] * 2 > m) return centroid(v, u, m);
    }
    return u;
}

void add(int u, int p, ll minCost, int val) {
    if (minCost >= 0) update(id[u], val);
    for (auto [v, w] : adj[u]) {
        if (v == p || del[v]) continue;
        add(v, u, min(a[v] - w, minCost + a[v] - w), val);
    }
}

void up(int u, int p, ll minCost, ll sum) {
    if (minCost >= 0) {
        ans++;
        costUp.push_back({sum, u});
    }
    for (auto [v, w] : adj[u]) {
        if (v == p || del[v]) continue;
        up(v, u, min(a[v] - w, minCost + a[v] - w), sum + a[v] - w);
    }
}

void down(int u, int p, ll minCost, ll sum) {
    if (minCost >= 0) ans++;

    auto it = lower_bound(costUp.begin(), costUp.end(), make_pair(-minCost, -1));
    if (it != costUp.end()) {
        int pos = it - costUp.begin() + 1;
        ans += get(sz) - get(pos - 1);
    }

    for (auto [v, w] : adj[u]) {
        if (v == p || del[v]) continue;
        down(v, u, min(minCost, sum + a[u] - w), sum + a[u] - w);
    }
}

void cd(int u) {
    int m = countChild(u, -1);
    u = centroid(u, -1, m);
    del[u] = 1;

    costUp.clear();
    for (auto [v, w] : adj[u]) if (!del[v])
        up(v, u, a[v] - w, a[v] - w);

    sort(costUp.begin(), costUp.end());
    sz = costUp.size();
    FOR(i, 0, sz - 1) id[costUp[i].S] = i + 1;

    for (auto [v, w] : adj[u]) if (!del[v])
        add(v, u, a[v] - w, 1);

    for (auto [v, w] : adj[u]) {
        if (del[v]) continue;
        add(v, u, a[v] - w, -1);
        down(v, u, a[u] - w, a[u] - w);
        add(v, u, a[v] - w, 1);
    }

    for (auto [v, w] : adj[u]) if (!del[v])
        add(v, u, a[v] - w, -1);
    costUp.clear();

    for (auto [v, w] : adj[u]) if (!del[v])
        cd(v);
}

void main_code() {
    cin >> numNode;
    FOR(i, 1, numNode) cin >> a[i];
    FOR(i, 1, numNode - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    cd(1);
    cout << ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0;
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); cout << "\n"; }
}

/* Lak lu theo dieu nhac */

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

Main.cpp: In function 'int main()':
Main.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100