Submission #855057

#	Time	Username	Problem	Language	Result	Execution time	Memory
855057		NeroZein	Love Polygon (BOI18_polygon)	C++17	100 / 100	172 ms	13368 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> matched(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) {
      matched[i] = true; 
    } 
    pq.emplace(deg[i], i); 
  }
  int ans = 0; 
  while (!pq.empty()) {
    auto [d, v] = pq.top();
    pq.pop(); 
    if (matched[v]) {
      continue;
    }
    ans++; 
    matched[v] = true;
    if (!matched[to[v]]) {//I deleted his edge as it's not pointing to me
      matched[to[v]] = true;
      deg[to[to[v]]]--;
      pq.emplace(deg[to[to[v]]], to[to[v]]); 
    }
  }
  cout << ans << '\n'; 
  return 0;
}

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