Submission #422848

#	Time	Username	Problem	Language	Result	Execution time	Memory
422848		Harry464	Love Polygon (BOI18_polygon)	C++14	100 / 100	690 ms	45756 KiB

polygon

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

vector<set <ll>> idg(100005);
vector<set <ll>> odg(100005);
map <string, ll> mapa;
map <string, bool> ima;

queue <ll> samci;
vector <ll> outcast;

ll neparni = 0;

int main()
{

    ll n;
    cin >> n;

    vector <string> prvi;
    vector <string> drugi;

    ll nodes = 0;

    for (int i = 0; i < n; i++){

        string a, b;
        cin >> a >> b;
        prvi.push_back(a), drugi.push_back(b);

        if (!ima[a])
            ima[a] = true, mapa[a] = nodes, nodes++;
        if (!ima[b])
            ima[b] = true, mapa[b] = nodes, nodes++;

    }

    if (n%2 == 1){

        cout << "-1" << endl;
        return 0;

    }

    for (int i = 0; i < n; i++)
        odg[mapa[prvi[i]]].insert(mapa[drugi[i]]), idg[mapa[drugi[i]]].insert(mapa[prvi[i]]);

    for (int i = 0; i < n; i++)
        if (idg[i].size() == 0)
          samci.push(i);

    ll brop = 0;

    //cout << "ok" << endl;

    vector <bool> vis(100000, false);

    for (int i = 0; i < n; i++){

        ll j = *odg[i].begin();
        if (i == j)
            continue;
        if (i == *odg[j].begin())
            vis[i] = true, vis[j] = true;

    }

    while (samci.size()){

        ll tren = samci.front();
        vis[tren] = true;
        samci.pop();

        ll ljubav = *odg[tren].begin();

        if (vis[ljubav]){

            idg[ljubav].erase(tren);
            outcast.push_back(tren);
            continue;

        }

        ll njljubav = *odg[ljubav].begin();

        vis[ljubav] = true;

        odg[ljubav].erase(njljubav);
        idg[njljubav].erase(ljubav);
        odg[ljubav].insert(tren);

        brop++;

        if (idg[njljubav].size() == 0 && !vis[njljubav])
            samci.push(njljubav);

        idg[tren].insert(ljubav);


    }

    //cout << brop << endl;

    //cout << "ok" << endl;

    for (int i = 0; i < n; i++){

        if (!vis[i]){

            ll pocetak = i;
            ll len = 1;
            ll tren = *odg[i].begin();
            vis[i] = true;
            while (tren != pocetak)
                vis[tren] = true, len++, tren = *odg[tren].begin();

            if (len == 2)
                    continue;

            if (len%2 == 0)
                brop += len/2;
            else
                brop += len/2, neparni++;

        }

    }

    ll rjes = brop + neparni + outcast.size();

    cout << rjes << endl;

}

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