oj.uz

Submission #232561

# Submission time Handle Problem Language Result Execution time Memory
232561 2020-05-17T10:50:05 Z Vimmer Transport (COCI19_transport) C++14
0 / 130
 786 ms 65540 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 500015
#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;

ll a[5002], h[5002], tin[5002], out[5002], in[5002], id, t[N][20], logs[N], pred[5002], pred_sum[5002], n;

ll ost[5002], dp[5002];

vector <ll> vr;

bool can[5002];

ll ans;

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

vector <ll> gr[5002];

ll calc(ll v, ll to, ll cur, ll mx, ll p)
{
    if (v == to) return mx;

    cur -= a[v];

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

        if (!(in[it.F] <= in[to] && out[to] <= out[it.F])) continue;

        return calc(it.F, to, cur, mx + max(0ll, cur + it.S), v);
    }
}

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

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

        cur += pred_sum[v];

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

    tin[v] = sz(vr);

    in[v] = id++;

    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);

        gr[v].pb(it.F);

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

    out[v] = id++;
}

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

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

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

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

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

    return v;
}
void rec(ll v, ll cur, ll mx, ll p)
{
    cur -= a[v];

    dp[v] = mx;

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

        rec(it.F, cur, mx + max(0ll, cur + it.S), v);
    }
}
void recr(ll v, ll p)
{
    memset(can, 0, sizeof(can));

    memset(ost, 0, sizeof(ost));

    memset(dp, 0, sizeof(dp));

    go(v, v, 0);

    rec(v, a[v], 0, p);

    for (ll i = 1; i <= n; i++)
    {
        if (i == v) continue;

        ll lc = lca(v, i);

        if (lc != i && lc != v)
        {
            if (can[lc] && ost[lc] >= calc(lc, i, a[lc], 0, pred[lc])) ans++;
        }
        else if (lc == i)
        {
            if (can[i]) ans++;
        }
        else
        {
            if (a[v] >= dp[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 (ll i = 2; i < N; i++) logs[i] = logs[i >> 1] + 1;

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

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

        cin >> a >> b >> c;

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

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

    dfs(1, -1);

    ll nm = sz(vr) - 1;

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

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

            ll 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;
}

Compilation message

transport.cpp: In function 'll calc(ll, ll, ll, ll, ll)':
transport.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 786 ms 18688 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 77 ms 65540 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 34 ms 32512 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 38 ms 32632 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 32 ms 32512 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 35 ms 32512 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 35 ms 32632 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 36 ms 32692 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 33 ms 32632 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 33 ms 32512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -