Submission #1268666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268666		rtri	Love Polygon (BOI18_polygon)	C++20	25 / 100	84 ms	17596 KiB

polygon

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

vector<int> points_to;
vector<set<int>> pointed_by;
vector<bool> solved;
int ans = 0;
int useless_count = 0;

void resolve_leaf(int u) {
  if (0 < pointed_by[u].size() || solved[u] || solved[points_to[u]])
    return;

  int par = points_to[u];
  int gpar = points_to[par];
  pointed_by[gpar].erase(par);

  for (auto v : pointed_by[par])
    if (v != u && 0 == pointed_by[v].size()) {
      useless_count++;
      solved[v] = 1;
    }

  points_to[points_to[u]] = u;
  pointed_by[u].insert(par);
  solved[u] = 1;
  solved[points_to[u]] = 1;
  ans++;

  resolve_leaf(gpar);
}

void resolve_cycle(int u, int sx = -1) {
  if (solved[u])
    return;
  if (u == sx)
    return;
  if (sx == -1)
    sx = u;

  int par = points_to[u];
  int gpar = points_to[par];

  if (par == sx) {
    ans += 1;
    solved[u] = 1;
    return;
  }

  solved[u] = 1;
  solved[par] = 1;
  ans++;

  if (gpar != sx)
    resolve_cycle(gpar);
}

int main() {
  int n;
  cin >> n;

  points_to.resize(n, -1);
  pointed_by.resize(n);

  unordered_map<string, int> name_to_idx;
  solved.resize(n);
  for (int i = 0; i < n; i++) {
    string a, b;
    cin >> a >> b;

    if (!name_to_idx.count(a))
      name_to_idx[a] = name_to_idx.size();
    if (!name_to_idx.count(b))
      name_to_idx[b] = name_to_idx.size();

    int aidx = name_to_idx[a], bidx = name_to_idx[b];

    // cerr << "[" << a << "][" << b << "]" << endl;
    // cerr << aidx << " " << bidx << endl;

    points_to[aidx] = bidx;
    pointed_by[bidx].insert(aidx);

    if (aidx == bidx) {
      solved[aidx] = 1;
      useless_count++;
    } else if (points_to[points_to[aidx]] == aidx) {
      solved[aidx] = 1;
      solved[bidx] = 1;
    }
  }

  if (n % 2 == 1) {
    cout << -1 << endl;
    return 0;
  }

  for (int a = 0; a < n; a++)
    resolve_leaf(a);

  for (int a = 0; a < n; a++)
    if (points_to[a] != a && !solved[a])
      resolve_cycle(a);

  ans += useless_count;

  cout << ans << endl;

  return 0;
}

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