제출 #232556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
232556		Vimmer	Transport (COCI19_transport)	C++14	0 / 130	1090 ms	44920 KiB

Main

#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[5002], h[5002], tin[5002], tout[5002], t[N][15], logs[N], pred[5002], pred_sum[5002], n;

ll ost[5002], dp[5002];

vector <int> vr;

bool can[5002];

ll ans;

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

vector <int> gr[5002];

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

    cur -= a[v];

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

        if (!(tin[it.F] <= tin[to] && tout[to] <= tout[it.F])) continue;

        return calc(it.F, to, 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[v] = 1; ost[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);

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

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

    tout[v] = sz(vr);

    vr.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 rec(int v, ll cur, ll mx, int 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(int v, int 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 (int i = 1; i <= n; i++)
    {
        if (i == v) continue;

        int 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 (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 < 15; 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13