Submission #1202112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202112		aykhn	Road Closures (APIO21_roads)	C++20	0 / 100	2093 ms	12372 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>

using namespace std;

const int MXN = 1e5 + 5;

int n, k;
int deg[MXN];
int used[MXN];
vector<array<long long, 3>> adj[MXN];

array<long long, 2> dfs(int a, int p, int cur, long long sum)
{
  if (sum > 0 && (cur == 0 || deg[a] < k)) return {a, sum};
  for (auto &[v, w, idx] : adj[a])
  {
    if (v == p) continue;
    if (used[idx] == cur)
    {
      if (!cur) 
      {
        array<long long, 2> x = dfs(v, a, cur ^ 1, sum + w);
        if (x[0] != -1) 
        {
          deg[a]++, deg[v]++;
          used[idx] ^= 1;
          return x;
        }
      }
      else 
      {
        array<long long, 2> x = dfs(v, a, cur ^ 1, sum - w);
        if (x[0] != -1) 
        {
          deg[a]--, deg[v]--;
          used[idx] ^= 1;
          return x;
        }
      }
    }
  }
  return {-1, 0};
}

vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) 
{
  n = N;
  long long all = 0;
  for (int i = 0; i < U.size(); i++)
  {
    long long u = U[i], v = V[i], w = W[i];
    adj[u].push_back({v, w, i});
    adj[v].push_back({u, w, i});
    all += w;
  }
  long long res = 0;
  vector<long long> v;
  for (k = 0; k < n; k++)
  {
    int F = 1;
    while (F)
    {
      F = 0;
      long long S = 0;
      for (int i = 0; i < n; i++)
      {
        if (deg[i] == k) continue;
        S += dfs(i, i, 0, 0)[1];
      }
      res += S;
      F = (S > 0);
    }
    v.push_back(all - res);
  }
  return v;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22