Submission #1053995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053995		vjudge1	Love Polygon (BOI18_polygon)	C++17	25 / 100	216 ms	26744 KiB

polygon

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

#define int long long
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << " " << (x) << endl;

struct DSU {
  vector<int> p, sz;
  DSU(int n) {
    p = vector<int>(n), sz = vector<int>(n, 1);
    iota(all(p), 0ll);
  }

  int find(int a) {
    if (a == p[a]) return p[a];
    return p[a] = find(p[a]);
  }

  void join(int u, int v) {
    int r1 = find(u);
    int r2 = find(v);
    if (r1 == r2) return;
    p[r2] = r1;
    sz[r1] += sz[r2];
  }
};

void solve() {
  int n;cin>>n;
  vector<pair<string, string>> a(n);
  set<string> st;
  map<string, int> mp;
  for (int i = 0; i < n; i++) {
    cin >> a[i].first >> a[i].second;
    st.insert(a[i].first);
    st.insert(a[i].second);
  }

  int m = 0;
  for (auto el : st) mp[el] = m++;

  DSU dsu(m);
  vector<int> nxt(m);
  for (int i = 0; i < n; i++) {
    dsu.join(mp[a[i].first], mp[a[i].second]);
    nxt[mp[a[i].first]] = mp[a[i].second];
  }
  
  int ans = 0;
  int leftover = 0;
  for (int i = 0; i < m; i++) {
    if (dsu.find(i) == i) {
      // debug(dsu.sz[i]);
      if (dsu.sz[i] & 1) leftover++;
      ans += dsu.sz[i]/2;
    }
  }

  if (leftover & 1) {
    cout << -1 << endl;
    return;
  }

  // debug(ans);
  int x = 0;
  for (int i = 0; i < m; i++) {
    if (nxt[nxt[i]] == i && nxt[i] != i) x++;
  }
  cout << ans + leftover - x/2 << endl;
}

int32_t main() {
  solve();
  return 0;
}

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