oj.uz

Submission #712070

# Submission time Handle Problem Language Result Execution time Memory
712070 2023-03-18T04:30:54 Z wenqi Love Polygon (BOI18_polygon) C++17
0 / 100
 61 ms 17428 KB 
// trans rights
#include <bits/extc++.h>
using namespace std;
using ll = long long;

int N;
unordered_map<string, int> mp;

int to[100069];
int cnt[100069];
bool taken[100069];

int main(int argc, const char *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    if (N & 1)
    {
        cout << -1;
        return 0;
    }
    int n = 1;
    for (int i = 0; i < N; i++)
    {
        string a, b;
        cin >> a >> b;
        int ia = mp[a], ib = mp[b];
        if (not ia)
            ia = mp[a] = n++;
        if (not ib)
            ib = mp[b] = n++;
        to[ia] = ib;
        cnt[ib]++;
    }
    priority_queue<pair<int, int>> pq;
    int ans = 0;
    for (int i = 1; i <= N; i++)
    {
        if (i == to[i])
        {
            ans++;
        }
        else if (i == to[to[i]])
        {
            taken[i] = true;
            taken[to[i]] = true;
        }
    }
    for (int i = 1; i <= N; i++)
    {
        if (not taken[i])
            pq.push({-cnt[i], i});
    }
    while (pq.size())
    {
        auto [k, i] = pq.top();
        pq.pop();
        if (-k != cnt[i] or taken[i])
            continue;
        ans++;
        if (taken[to[i]])
        {
            continue;
        }
        cnt[to[to[i]]]--;
        pq.push({-cnt[to[to[i]]], to[to[i]]});
        taken[i] = taken[to[i]] = true;
    }
    cout << ans;
    return 0;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 17428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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