oj.uz

Submission #422803

# Submission time Handle Problem Language Result Execution time Memory
422803 2021-06-10T12:38:19 Z Harry464 Love Polygon (BOI18_polygon) C++14
54 / 100
 671 ms 45788 KB 
#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";
        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);

    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);

        brop++;

        if (idg[njljubav].size() == 0)
            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;

}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9716 KB Output is correct
4 Correct 6 ms 9688 KB Output is correct
5 Correct 6 ms 9700 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9696 KB Output is correct
8 Incorrect 6 ms 9676 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 575 ms 43168 KB Output is correct
5 Correct 588 ms 43160 KB Output is correct
6 Correct 594 ms 43056 KB Output is correct
7 Correct 380 ms 33684 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 43524 KB Output is correct
2 Correct 671 ms 43352 KB Output is correct
3 Correct 443 ms 43180 KB Output is correct
4 Correct 327 ms 33688 KB Output is correct
5 Correct 591 ms 43172 KB Output is correct
6 Correct 607 ms 43920 KB Output is correct
7 Correct 599 ms 44164 KB Output is correct
8 Correct 531 ms 43600 KB Output is correct
9 Correct 591 ms 44660 KB Output is correct
10 Correct 439 ms 45788 KB Output is correct
11 Correct 7 ms 9676 KB Output is correct
12 Correct 6 ms 9692 KB Output is correct
13 Correct 7 ms 9676 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9716 KB Output is correct
4 Correct 6 ms 9688 KB Output is correct
5 Correct 6 ms 9700 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9696 KB Output is correct
8 Incorrect 6 ms 9676 KB Output isn't correct
9 Halted 0 ms 0 KB -