oj.uz

Submission #855047

# Submission time Handle Problem Language Result Execution time Memory
855047 2023-09-30T01:54:57 Z NeroZein Love Polygon (BOI18_polygon) C++17
25 / 100
 182 ms 11036 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> vis(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) {
      vis[i] = true; 
    } else {
      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;
    }
    seen[v] = true;
    if (to[v] == v) {
      ans++;
      continue;
    }
    deg[to[v]]--;
    pq.emplace(deg[to[v]], to[v]); 
    if (!vis[v]) {
      ans++;
      vis[to[v]] = true;
    }
  }
  cout << ans << '\n'; 
  return 0;
}

Subtask #1
0 / 21.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 182 ms 10856 KB Output is correct
5 Correct 169 ms 10980 KB Output is correct
6 Correct 177 ms 11036 KB Output is correct
7 Correct 145 ms 9808 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
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 -