Submission #232503

#	Time	Username	Problem	Language	Result	Execution time	Memory
232503		VEGAnn	Transport (COCI19_transport)	C++14	130 / 130	417 ms	15860 KiB

Main

#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MP make_pair
#define PB push_back
#define ft first
#define sd second
#define sz(x) ((int)x.size())
#define pil pair<int,ll>
#define pli pair<ll,ll>
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
const int N = 100100;
const int oo = 2e9;
vector<ll> vc;
int fen[N];
vector<pil> g[N];
ll ans = 0, a[N];
int n, siz[N];
bool mrk[N];

void build_sz(int v, int p){
    siz[v] = 1;

    for (pil u : g[v]){
        if (u.ft == p || mrk[u.ft]) continue;

        build_sz(u.ft, v);

        siz[v] += siz[u.ft];
    }
}

int search(int v, int p, int SZ){
    for (pil u : g[v])
        if (u.ft != p && !mrk[u.ft] && siz[u.ft] > SZ / 2)
            return search(u.ft, v, SZ);
    return v;
}

int calc(ll x){
    x = upper_bound(all(vc), x) - vc.begin() - 1;
    int res = 0;

    for (; x >= 0; x = (x & (x + 1)) - 1)
        res += fen[x];

    return res;
}

void check_up(int v, int p, ll sm, int p_ed, ll sf){
    sf = min(sf - p_ed + a[v], 0ll);
    sm += a[v] - p_ed;

    if (sf == 0) {
        ans += calc(sm);
    }

    for (pil u : g[v]) {
        if (u.ft == p || mrk[u.ft]) continue;
        check_up(u.ft, v, sm, u.sd, sf);
    }
}

void real_insrt(int v, int p, int p_ed, ll sm, ll mn, ll sta){
    mn = min(mn, sm - p_ed);

    vc.PB(-mn);

    sm += a[v] - p_ed;

    if (-mn <= sta)
        ans++;

    for (pil u : g[v]){
        if (u.ft == p || mrk[u.ft]) continue;
        real_insrt(u.ft, v, u.sd, sm, mn, sta);
    }
}

void update(ll vl){
    int id = lower_bound(all(vc), vl) - vc.begin();

    for (; id < sz(vc); id = (id | (id + 1)))
        fen[id]++;
}

void insrt(int v, int p, int p_ed, ll sm, ll mn){
    mn = min(mn, sm - p_ed);

//    st.insert(MP(-mn, v));
    update(-mn);

    sm += a[v] - p_ed;

    for (pil u : g[v]){
        if (u.ft == p || mrk[u.ft]) continue;
        insrt(u.ft, v, u.sd, sm, mn);
    }
}

void build_cd(int v){
    build_sz(v, -1);

    v = search(v, -1, siz[v]);

    vc.clear();
    vc.PB(0);

    for (pil u : g[v]){
        if (mrk[u.ft]) continue;

        real_insrt(u.ft, v, u.sd, 0, 0, a[v]);
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < sz(vc); i++)
        fen[i] = 0;

    update(0);

    for (int it = 0; it < sz(g[v]); it++){
        pil u = g[v][it];

        if (mrk[u.ft]) continue;

        check_up(u.ft, v, a[v], u.sd, 0);

        insrt(u.ft, v, u.sd, 0, 0);
    }

    for (int i = 0; i < sz(vc); i++)
        fen[i] = 0;

    for (int it = sz(g[v]) - 1; it >= 0; it--){
        pil u = g[v][it];

        if (mrk[u.ft]) continue;

        check_up(u.ft, v, a[v], u.sd, 0);

        insrt(u.ft, v, u.sd, 0, 0);
    }

    mrk[v] = 1;

    for (pil u : g[v])
        if (!mrk[u.ft])
            build_cd(u.ft);
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 1; i < n; i++){
        int x, y, w; cin >> x >> y >> w;
        x--; y--;

        g[x].PB(MP(y, w));
        g[y].PB(MP(x, w));
    }

    build_cd(0);

    cout << ans;

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13