oj.uz

Submission #855050

# Submission time Handle Problem Language Result Execution time Memory
855050 2023-09-30T02:03:11 Z NeroZein Love Polygon (BOI18_polygon) C++17
0 / 100
 178 ms 10836 KB 
#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.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

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