#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++;
if (!matched[to[v]]) {//I deleted his edge as it's not pointing to me
deg[to[v]]--;
matched[v] = true;
matched[to[v]] = true;
pq.emplace(deg[to[v]], to[v]);
}
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
158 ms |
10908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
