Submission #1322383

#TimeUsernameProblemLanguageResultExecution timeMemory
1322383repmannNestabilnost (COI23_nestabilnost)C++20
12 / 100
80 ms20348 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N;
int A[300001], F[300001], MIN[300001];
int pos, ET[300001];
ll DP[300002];
vector <int> VG[300001];
void DFS(int node, int parent = 0)
{
  ET[++pos] = node;
  for(int x : VG[node]) if(x != parent) DFS(x, node);
  return;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N;
  for(int i = 1; i <= N; i++) cin >> A[i];
  for(int i = 1; i <= N; i++) cin >> F[i];
  MIN[N] = F[N];
  for(int i = N - 1; i; i--) MIN[i] = min(MIN[i + 1], F[i]);
  int u, v;
  for(int i = 1; i < N; i++)
  {
    cin >> u >> v;
    VG[u].push_back(v);
    VG[v].push_back(u);
  }
  if(N > 5000) return 0;
  for(int i = 1; i <= N; i++) if(VG[i].size() > 2) return 0;
  DFS(1);
  for(int i = N; i; i--)
  {
    DP[ET[i]] = MIN[A[ET[i]] + 1] + DP[ET[i + 1]];
    int k = A[ET[i]] + 1;
    bool flag = false;
    for(int j = i + 1; j <= N; j++)
    {
      if(A[ET[j]] == (A[ET[j - 1]] + 1))
      {
        if(flag && (A[ET[j]] >= k)) break;
        k = max(k, A[ET[j]] + 1);
      }
      else if(!A[ET[j]])
      {
        if(flag && (k != (A[ET[j - 1]] + 1))) break;
        if(k > (A[ET[j - 1]] + 1)) break;
        k = A[ET[j - 1]] + 1;
        flag = true;
      }
      else break;
      if(flag) DP[ET[i]] = min(F[k] + DP[ET[j + 1]], DP[ET[i]]);
      else DP[ET[i]] = min(MIN[k] + DP[ET[j + 1]], DP[ET[i]]);
    }
  }
  cout << DP[1] << '\n';

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...