oj.uz

Submission #232497

# Submission time Handle Problem Language Result Execution time Memory
232497 2020-05-17T08:13:19 Z VEGAnn Transport (COCI19_transport) C++14
130 / 130
 908 ms 23812 KB 
#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.0 / 13.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3456 KB Output is correct
2 Correct 28 ms 3712 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 11896 KB Output is correct
2 Correct 240 ms 11000 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 15356 KB Output is correct
2 Correct 435 ms 17016 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 19960 KB Output is correct
2 Correct 708 ms 23812 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 6988 KB Output is correct
2 Correct 87 ms 6272 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 9672 KB Output is correct
2 Correct 274 ms 9080 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 12144 KB Output is correct
2 Correct 367 ms 12408 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 14780 KB Output is correct
2 Correct 551 ms 14840 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 18592 KB Output is correct
2 Correct 767 ms 16888 KB Output is correct