Submission #842264

#	Time	Username	Problem	Language	Result	Execution time	Memory
842264		WLZ	Logičari (COCI21_logicari)	C++17	110 / 110	79 ms	36608 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MAXN = (int) 1e5;
const int INF = 0x3f3f3f3f;

class dsu {
  private: vector<int> p, rank, sz;
  public:
    dsu(int n) {
      p.assign(n, -1);
      rank.assign(n, 0);
      sz.assign(n, 1);
    }

    int root(int x) {
      if (p[x] == -1) return x;
      return p[x] = root(p[x]);
    }

    bool connected(int x, int y) {
      return root(x) == root(y);
    }

    void connect(int x, int y) {
      x = root(x); y = root(y);
      if (x != y) {
        if (rank[x] > rank[y]) p[y] = x, sz[x] += sz[y];
        else {
          p[x] = y;
          sz[y] += sz[x];
          if (rank[x] == rank[y]) rank[y]++;
        }
      }
    }

    int size(int x) {
      return sz[root(x)];
    }
};

int n, root, special;
vector< vector<int> > g;
long long dp[MAXN + 1][2][2][2][2];

void dfs(int u, int p) {
  for (auto &v : g[u]) if (v != p) dfs(v, u);
  for (int val = 0; val < 2; val++) {
    for (int up = 0; up < 2; up++) {
      for (int rt = 0; rt < 2; rt++) {
        for (int sp = 0; sp < 2; sp++) {
          if (u == special && rt && up) continue;
          if (u == root && rt != val) continue;
          if (u == special && sp != val) continue;
          if (p == root && rt != up) continue;
          if (u == root && up) continue;
          bool found = (u == root && sp) || (u == special && rt) || up;
          long long tmp = val;
          for (auto &v : g[u]) if (v != p) tmp += dp[v][0][val][rt][sp];
          if (found) dp[u][val][up][rt][sp] = tmp;
          else for (auto &v : g[u]) if (v != p) dp[u][val][up][rt][sp] = min((long long) dp[u][val][up][rt][sp], tmp - dp[v][0][val][rt][sp] + dp[v][1][val][rt][sp]);
        }
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  g.resize(n + 1);
  dsu g2(n + 1);
  for (int i = 0; i < n; i++) {
    int u, v;
    cin >> u >> v;
    if (g2.connected(u, v)) root = u, special = v;
    else {
      g[u].push_back(v);
      g[v].push_back(u);    
    }
    g2.connect(u, v);
  }
  for (int u = 1; u <= n; u++) for (int val = 0; val < 2; val++) for (int up = 0; up < 2; up++) for (int rt = 0; rt < 2; rt++) for (int sp = 0; sp < 2; sp++) dp[u][val][up][rt][sp] = INF;
  dfs(root, -1);
  long long ans = INF;
  for (int val = 0; val < 2; val++) for (int up = 0; up < 2; up++) for (int rt = 0; rt < 2; rt++) for (int sp = 0; sp < 2; sp++) ans = min(ans, dp[root][val][up][rt][sp]);
  if (ans == INF) cout << -1 << '\n';
  else cout << ans << '\n';
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 50 / 50