oj.uz

Submission #855046

# Submission time Handle Problem Language Result Execution time Memory
855046 2023-09-30T01:54:19 Z NeroZein Love Polygon (BOI18_polygon) C++17
25 / 100
 174 ms 13248 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(0, 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 163 ms 13024 KB Output is correct
5 Correct 166 ms 13056 KB Output is correct
6 Correct 165 ms 13248 KB Output is correct
7 Correct 146 ms 11936 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 13004 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 -