Submission #855050

#	Time	Username	Problem	Language	Result	Execution time	Memory
855050		NeroZein	Love Polygon (BOI18_polygon)	C++17	0 / 100	178 ms	10836 KiB

polygon

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  int id = 0; 
  map<string, int> mp;
  vector<int> to(n * 2); 
  vector<int> deg(n * 2); 
  for (int i = 0; i < n; ++i) {
    string s1, s2;
    cin >> s1 >> s2;
    if (!mp.count(s1)) {
      mp[s1] = id++; 
    }
    if (!mp.count(s2)) {
      mp[s2] = id++; 
    }
    if (s1 != s2) {
      deg[mp[s2]]++;       
    }
    to[mp[s1]] = mp[s2]; 
  }
  if (n % 2) {
    cout << -1 << '\n';
    return 0; 
  }
  vector<bool> match(id); 
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 
  for (int i = 0; i < id; ++i) {
    if (to[i] != i && to[to[i]] == i) {
      match[i] = true; 
    } 
    pq.emplace(deg[i], i); 
  }
  vector<bool> seen(n); 
  int ans = 0; 
  while (!pq.empty()) {
    auto [d, v] = pq.top();
    pq.pop(); 
    if (seen[v]) {
      continue;
    }
    deg[to[v]]--; 
    pq.emplace(to[v], v); 
    seen[v] = true;
    if (!match[v] && !match[to[v]]) {
      ans++; 
      match[v] = true;
      match[to[v]] = true;
    } else if (!match[v]) {
      ans++; 
    }
  }
  cout << ans << '\n'; 
  return 0;
}

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