oj.uz

Submission #232503

# Submission time Handle Problem Language Result Execution time Memory
232503 2020-05-17T08:29:55 Z VEGAnn Transport (COCI19_transport) C++14
130 / 130
 417 ms 15860 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2944 KB Output is correct
2 Correct 12 ms 3072 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3200 KB Output is correct
2 Correct 16 ms 3456 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 8564 KB Output is correct
2 Correct 91 ms 8064 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 10616 KB Output is correct
2 Correct 157 ms 11888 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 13680 KB Output is correct
2 Correct 251 ms 15860 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 4984 KB Output is correct
2 Correct 51 ms 4608 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 6380 KB Output is correct
2 Correct 151 ms 6036 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 7288 KB Output is correct
2 Correct 211 ms 7540 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 8820 KB Output is correct
2 Correct 339 ms 8944 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 10736 KB Output is correct
2 Correct 399 ms 10100 KB Output is correct