Submission #821803

#	Time	Username	Problem	Language	Result	Execution time	Memory
821803		tch1cherin	Love Polygon (BOI18_polygon)	C++17	100 / 100	290 ms	34796 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 1e5 + 5;
vector<int> G[MAX_N], comp;
bool vis[MAX_N] = {};
int dp[MAX_N][2] = {};
 
void DFS(int u, pair<int, int> edge = {-1, -1}) {
  vis[u] = true;
  dp[u][0] = dp[u][1] = 0;
  vector<int> children;
  for (int v : G[u]) {
    if (u == edge.first && v == edge.second) {
      continue;
    }
    if (v == edge.first && u == edge.second) {
      continue;
    }
    if (!vis[v]) {
      children.push_back(v);
      DFS(v, edge);
      dp[u][0] += max(dp[v][0], dp[v][1]);
    }
  }
  dp[u][1] = dp[u][0];
  for (int v : children) {
    if (u == edge.first && v == edge.second) {
      continue;
    }
    if (v == edge.first && u == edge.second) {
      continue;
    }
    dp[u][1] = max(dp[u][1], dp[u][0] - max(dp[v][0], dp[v][1]) + dp[v][0] + 1);
  }
  comp.push_back(u);
}
 
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;
  map<string, int> val;
  int max_v = 0;
  vector<int> in_degree(N), go(N);
  for (int i = 0; i < N; i++) {
    string A, B;
    cin >> A >> B;
    if (!val.count(A)) {
      val[A] = max_v++;
    }
    if (!val.count(B)) {
      val[B] = max_v++;
    }
    go[val[A]] = val[B];
    if (val[A] != val[B]) {
      in_degree[val[A]]++;
      G[val[B]].push_back(val[A]);
    }
  }
  if (N % 2) {
    cout << -1 << "\n";
    exit(0);
  }
  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (go[go[i]] == i && !vis[i] && go[i] != i) {
      ans += 2;
      for (int v : G[i]) {
        in_degree[v]--;
      }
      for (int v : G[go[i]]) {
        in_degree[v]--;
      }
      vis[i] = vis[go[i]] = true;
    }
  }
  for (int i = 0; i < N; i++) {
    if (in_degree[i] == 0 && !vis[i]) {
      comp = vector<int>();
      DFS(i);
      ans += max(dp[i][0], dp[i][1]);
    }
  }
  vector<bool> used(N, false), in_cycle(N, false);
  vector<int> prv(N);
  for (int i = 0; i < N; i++) {
    if (!vis[i] && !used[i]) {
      used[i] = true;
      int j = go[i];
      vector<int> cycle;
      cycle.push_back(i);
      while (!used[j]) {
        used[j] = true;
        cycle.push_back(j);
        j = go[j];
      }
      bool occ = false;
      int last = cycle.back();
      for (int v : cycle) {
        if (v == j) {
          occ = true;
        }
        if (occ) {
          in_cycle[v] = true;
          prv[v] = last;
          last = v;
        }
      }
    }
  }
  for (int i = 0; i < N; i++) {
    if (in_cycle[i] && !vis[i]) {
      comp = vector<int>();
      DFS(i, {i, go[i]});
      int res = max(dp[i][0], dp[i][1]);
      for (int v : comp) {
        vis[v] = false;
      }
      DFS(prv[i], {i, prv[i]});
      res = max({res, dp[prv[i]][0], dp[prv[i]][1]});
      ans += res;
    }
  }
  cout << N - ans << "\n";
}

• Subtask 1: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 25 / 25