oj.uz

Submission #1053994

# Submission time Handle Problem Language Result Execution time Memory
1053994 2024-08-12T03:14:44 Z vjudge1 Love Polygon (BOI18_polygon) C++17
0 / 100
 197 ms 26704 KB 
#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) x++;
  }
  cout << ans + leftover - x/2 << endl;
}

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

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 26704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -