Submission #232497

#	Time	Username	Problem	Language	Result	Execution time	Memory
232497		VEGAnn	Transport (COCI19_transport)	C++14	130 / 130	908 ms	23812 KiB

Main

#include <bits/stdc++.h>
#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>
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;
ordered_set<pli> st;
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;
}

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 += st.order_of_key(MP(sm, oo));

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

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

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

    sm += a[v] - p_ed;

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

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

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

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

    st.clear();
    st.insert(MP(0, v));

    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, a[v]);
    }

    st.clear();

    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, -1);
    }

    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