제출 #1307444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307444		pvpro	Nestabilnost (COI23_nestabilnost)	C++20	7 / 100	1599 ms	394940 KiB

code1

#ifndef LOCAL
#pragma GCC Optimize("O3,Ofast,unroll-loops")
#pragma GCC Target("bmi,bmi2,avx,avx2")
#endif
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define int ll

#define f first 
#define s second 
#define mp make_pair 
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin() (x).rend()
#ifndef LOCAL
#define endl "\n"
#endif

mt19937 rnd(11);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) {
        cin >> x;
    }
    vector<int> f(n);
    for (auto &x : f) {
        cin >> x;
    }
    f.insert(f.begin(), 0);
    vector<int> suffmin = f;
    for (int i = n; i > 0; --i) {
        suffmin[i - 1] = min(suffmin[i], suffmin[i - 1]);
    }
    vector<vector<int>> graph(n);
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    vector<map<int, int>> A(n), B(n);
    auto get = [&](int ind, int x, bool eq = false) {
        int answer = 1e18;
        if (B[ind].count(x) && eq) {
            answer = B[ind][x];
        }
        for (auto &y : A[ind]) {
            if (y.f <= x) {
                answer = min(answer, y.s);
            }
        }
        return answer;
    };
    auto dfs = [&](int v, int prev, auto &&self) -> int {
        int ans = v;
        A[ans][0] = suffmin[a[v] + 1];
        A[ans][a[v] + 1] = 0;
        for (auto &u : graph[v]) {
            if (u != prev) {
                int res = self(u, v, self);
                int delta = get(res, 0);
                if (a[u] > 0 && a[u] != a[v] + 1) {
                    for (auto &x : A[ans]) {
                        x.s += delta;
                    }
                    for (auto &x : B[ans]) {
                        x.s += delta;
                    }
                } else {
                    if (a[u] > 0) {
                        for (auto &x : A[res]) {
                            A[ans][x.f] = get(ans, x.f);
                        }
                        for (auto &x : B[res]) {
                            B[ans][x.f] = get(ans, x.f, true);
                        }
                        for (auto &x : A[ans]) {
                            x.s += get(res, x.f);
                        }
                        for (auto &x : B[ans]) {
                            x.s += get(res, x.f, true);
                        }
                    } else {
                        int k = a[v] + 1;
                        int now = get(ans, k, true);
                        B[ans][k] = now + get(res, k, true);
                        for (auto &x : A[ans]) {
                            x.s += delta;
                        }
                        for (auto &x : B[ans]) {
                            if (x.f != k) {
                                x.s += delta;
                            }
                        }
                    }
                }
            }
        }
        for (auto &x : B[ans]) {
            A[ans][0] = min(A[ans][0], x.s + f[x.f]);
        }
        for (auto &x : A[ans]) {
            A[ans][0] = min(A[ans][0], x.s + suffmin[x.f]);
        }
        return ans;
    };
    auto ans = dfs(0, 0, dfs);
    cout << get(ans, 0) << endl;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else
        ios::sync_with_stdio(false);
        cin.tie(0);
    #endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 20
• Subtask 3: 7 / 7
• Subtask 4: 0 / 22
• Subtask 5: 0 / 39