oj.uz

Submission #232538

# Submission time Handle Problem Language Result Execution time Memory
232538 2020-05-17T10:13:42 Z Vimmer Transport (COCI19_transport) C++14
0 / 130
 186 ms 65536 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>



//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define sz(x) ll(x.size())
#define N 100015
#define base 1000000
#define M ll(1e9+7)
#define F first
#define S second
#define pb push_back
#define in insert
#define eb emplace_back
#define ed "\n"

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef short int si;

//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int a[N], h[N], tin[N], t[N * 4][20], logs[N * 4], pred[N], pred_sum[N], n;

vector <int> vr;

ll ans;

ll dp[5002][5002], ost[5002][5002];

bool can[5002][5002];

vector <pair <int, int> > g[N];

vector <int> gr[5002];

void rec(int v, int from, ll cur, ll mx, int p)
{
    if (v != from) cur -= a[v];

    if (v != from) dp[from][v] = mx;

    for (auto it : g[v])
    {
        if (it.F == p) continue;

        rec(it.F, from, cur, mx + max(0ll, cur + it.S), v);
    }
}

void go(int v, int from, ll cur)
{
    while (cur <= 0 && v != 0)
    {
        cur -= a[v];

        if (v != from) {can[from][v] = 1; ost[from][v] = abs(cur);}

        cur += pred_sum[v];

        v = pred[v];
    }
}
void dfs(int v, int p)
{
    if (p != -1) h[v] = h[p] + 1;

    tin[v] = sz(vr);

    vr.pb(v);

    for (auto it : g[v])
    {
        if (p == it.F) continue;

        pred[it.F] = v;

        pred_sum[it.F] = it.S;

        dfs(it.F, v);

        vr.pb(v);

        for (auto itr : gr[it.F]) gr[v].pb(itr);
    }

    rec(v, v, 0, 0, p);

    go(v, v, 0);

    gr[v].pb(v);
}

int lca(int a, int b)
{
    if (tin[a] > tin[b]) swap(a, b);

    int j = logs[tin[b] - tin[a] + 1];

    int v = t[tin[a]][j];

    int vt = t[tin[b] - (1 << j) + 1][j];

    if (h[v] > h[vt]) return vt;

    return v;
}

void recr(int v, int p)
{
    for (int i = 1; i <= n; i++)
    {
        if (i == v) continue;

        int lc = lca(v, i);

        if (lc != i && lc != v)
        {
            if (can[v][lc] && ost[v][lc] >= dp[lc][i]) ans++;
        }
        else if (lc == i)
        {
            if (can[v][lc]) ans++;
        }
        else
        {
            if (a[v] >= dp[v][i]) ans++;
        }
    }

    for (auto it : g[v])
    {
        if (it.F == p) continue;

        recr(it.F, v);
    }
}
int main()
{
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 2; i < N; i++) logs[i] = logs[i >> 1] + 1;

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

    for (int i = 1; i < n; i++)
    {
        int a, b, c;

        cin >> a >> b >> c;

        g[a].pb({b, c});

        g[b].pb({a, c});
    }

    dfs(1, -1);

    int nm = sz(vr) - 1;

    for (int i = 0; i <= nm; i++) t[i][0] = vr[i];

    for (int j = 1; j < 20; j++)
        for (int i = 0; i <= nm; i++)
        {
            int v = t[i][j - 1];

            int vt = t[min(i + (1 << (j - 1)), nm)][j - 1];

            if (h[v] > h[vt]) t[i][j] = vt; else t[i][j] = v;
        }

    recr(1, -1);

    cout << ans << endl;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 39552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 18296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 22648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 28404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 112 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 10620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 11512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 12792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -