Submission #930090

#	Time	Username	Problem	Language	Result	Execution time	Memory
930090		Karoot	Love Polygon (BOI18_polygon)	C++17	100 / 100	249 ms	20272 KiB

polygon

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

const int MAXN = 2e5+1;
int indeg[MAXN];
int parent[MAXN];
bool don[MAXN];

int counter = 0;

map<int, string> M;
map<string, int> person;
vector<int> single;

vector<int> ans;

int main(){
    scoobydoobydoo();
    int n; cin >> n;
    for (int i = 0; i < n; i++){
        string a, b; cin >> a >> b;
        if (person.find(a) == person.end()){
            person[a] = counter++;
            M[person[a]] = a;
        }
        if (person.find(b) == person.end()){
            person[b] = counter++;
            M[person[b]] = b;
        }
        parent[person[a]] = person[b];
    }

    if (n%2){
        cout << -1 << endl;
        return 0;
    }


    //filter relationships
    for (int i = 0; i < counter; i++){
        if (!don[i] && parent[parent[i]] == i && parent[i] != i){
            don[i] = true;
            don[parent[i]] = true;
        }
    }

    for (int i = 0; i < counter; i++){
        if (don[i])continue;
        if (don[parent[i]] || parent[i] == i)parent[i] = -1;
        else indeg[parent[i]]++;
    }

    queue<int> q;

    for (int i = 0; i < counter; i++){
        if (don[i])continue;
        if (parent[i] == -1 && indeg[i] == 0)single.push_back(i);
        else if (indeg[i] == 0)q.push(i);
    }

    while (!q.empty()){
        int node = q.front();
        int pare = parent[node];
        q.pop();
        if (don[pare]){
            single.push_back(node);
            don[node] = true;
            continue;
        }
        ans.push_back(pare);
        indeg[parent[pare]]--;
        don[node] = true;
        don[pare] = true;
        if (parent[parent[pare]] == -1 && indeg[parent[pare]] == 0)single.push_back(parent[pare]);
        else if (indeg[parent[pare]] == 0)q.push(parent[pare]);
    }

    //cout << (int)ans.size() << endl;
    //cout << single.size() << endl;

    for (int i = 0; i < counter; i++){
        if (!don[i] && indeg[i] == 1 && parent[i] != -1){
            don[i] = true;
            //cout << "inhere: " << i << endl;
            if (don[parent[i]]){
                don[i] = true;
                single.push_back(i);
                continue;
            }
            don[parent[i]] = true;
            indeg[parent[parent[i]]]--;
            ans.push_back(parent[i]);
            if (indeg[parent[parent[i]]] == 0)q.push(parent[parent[i]]);

            while (!q.empty()){
                int node = q.front();
                int pare = parent[node];
                q.pop();
                if (don[node])continue;
                if (don[pare]){
                    single.push_back(node);
                    don[node] = true;
                    continue;
                }
                ans.push_back(pare);
                indeg[parent[pare]]--;
                don[node] = true;
                don[pare] = true;
                if ((parent[parent[pare]] == -1 || don[parent[parent[pare]]]) && indeg[parent[pare]] == 0 && !don[parent[pare]] && parent[parent[pare]] != i)single.push_back(parent[pare]);
                else if (indeg[parent[pare]] == 0)q.push(parent[pare]);
            }
        }
    }

    /*
10 
a a
b c
c d
d e
e f
f b
g c
h g
i c
j g
    
    
    
    */


    //pair singles

    /*cout << "ordinary" << endl;
    for (auto& e : ans)cout << e << " ";
    cout << endl;
    

    cout << "singles" << endl;*/
    
    for (int i = 0; i < single.size(); i++){
        ans.push_back(single[i]);
        //cout << single[i] << " ";
    }
    //cout << endl;


    cout << ans.size() << endl;





    return 0;
}

Compilation message (stderr)

polygon.cpp: In function 'int main()':
polygon.cpp:165:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for (int i = 0; i < single.size(); i++){
      |                     ~~^~~~~~~~~~~~~~~

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