Submission #465037

#	Time	Username	Problem	Language	Result	Execution time	Memory
465037		JovanB	Love Polygon (BOI18_polygon)	C++17	100 / 100	262 ms	11468 KiB

polygon

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 100000;

map <string, int> u;
bool taken[N+5];
int f[N+5];
int deg[N+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    int tjm = 0;
    for(int i=1; i<=n; i++){
        string _a, _b;
        cin >> _a >> _b;
        if(!u[_a]) u[_a] = ++tjm;
        if(!u[_b]) u[_b] = ++tjm;
        int a = u[_a], b = u[_b];
        f[a] = b;
        deg[b]++;
    }
    if(n%2){
        cout << "-1\n";
        return 0;
    }
    int cnt = 0;
    queue <int> q;
    for(int i=1; i<=n; i++){
        if(f[f[i]] == i && f[i] != i) cnt++, taken[i] = 1;
        else if(deg[i] == 0) q.push(i);
    }
    while(!q.empty()){
        int v = q.front();
        q.pop();
        if(!taken[f[v]] && !taken[v] && v != f[v]){
            taken[f[v]] = 1, taken[v] = 1, cnt++;
            if(f[f[v]] != f[v]){
                deg[f[f[v]]]--;
                if(deg[f[f[v]]] == 0) q.push(f[f[v]]);
            }
            deg[v] = deg[f[v]] = -1;
        }
        else{
            deg[f[v]]--;
            if(deg[f[v]] == 0) q.push(f[v]);
        }
    }
    for(int i=1; i<=n; i++){
        if(!taken[i]){
            int tr = 1;
            taken[i] = 1;
            int x = f[i];
            while(x != i && !taken[x]){
                tr++;
                taken[x] = 1;
                x = f[x];
            }
            cnt += tr/2;
        }
    }
    cout << n - cnt << "\n";
    return 0;
}

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