Submission #446503

#	Time	Username	Problem	Language	Result	Execution time	Memory
446503		prvocislo	Love Polygon (BOI18_polygon)	C++17	100 / 100	224 ms	12108 KiB

polygon

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    if (n%2)
    {
        cout << "-1" << endl;
        return 0; 
    }
    map<string, int> m;
    vector<int> il(n, -1), lm(n, 0), happy(n, 0); // koho ja lubim, kolko postav lubi mna?
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        string a, b;
        cin >> a >> b;
        if (!m.count(a)) m[a] = cnt++;
        if (!m.count(b)) m[b] = cnt++;
        int ia = m[a], ib = m[b];
        il[ia] = ib, lm[ib]++;
        if (ia != ib && il[ib] == ia) happy[ia] = happy[ib] = true;
    }
    vector<int> stk;
    for (int i = 0; i < n; i++)
        if (lm[i] == 0) stk.push_back(i);
    int ans = 0, alone = 0;
    while (!stk.empty())
    {
        int i = stk.back(); stk.pop_back();
        if (happy[il[i]])
        {
            alone++;
            happy[i] = true;
            continue;
        }
        happy[i] = happy[il[i]] = true;
        ans++;
        if (!happy[il[il[i]]])
        {
            lm[il[il[i]]]--;
            if (!lm[il[il[i]]]) stk.push_back(il[il[i]]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (happy[i]) continue;
        int j = il[i], len = 1;
        happy[i] = true;
        while (j != i)
        {
            happy[j] = true;
            len++;
            j = il[j];
        }
        ans += (len>>1), alone += (len&1);
    }
    cout << ans+alone << "\n";
    return 0;
}

• Subtask 1: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 25 / 25