제출 #1124616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124616		codexistent	Love Polygon (BOI18_polygon)	C++20	100 / 100	339 ms	16792 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define ll long long
#define FOR(i, a, b) for(ll i = a; i <= b; i++)

ll n, v[MAXN], deg[MAXN], nx[MAXN], r = 0;
vector<ll> prv[MAXN];
map<string, ll> mp;

int main(){
    cin >> n;
    ll nc = 0;
    if(n % 2) return cout << -1 << endl, 0;
    FOR(i, 1, n){
        string x, y; cin >> x >> y;
        if(mp.find(x) == mp.end()) mp.insert({x, ++nc});
        if(mp.find(y) == mp.end()) mp.insert({y, ++nc});

        nx[mp[x]] = mp[y];
        deg[mp[y]] += (mp[x] != mp[y]), prv[mp[y]].push_back(mp[x]);
    }

    queue<ll> q;
    FOR(i, 1, n) {
        if(!deg[i]) q.push(i);
        v[i] = i == nx[nx[i]] && i != nx[i];
    }
    while(q.size()){
        ll qi = q.front(); q.pop();
        if(v[qi] || v[nx[qi]] || qi == nx[qi]) continue;

        v[qi] = v[nx[qi]] = true, r++;
        if(!v[nx[nx[qi]]] && !(--deg[nx[nx[qi]]])){
            q.push(nx[nx[qi]]);
        }
    }
    FOR(st, 1, n) if(!v[st]){
        ll sc = 0, i = st;
        while(!v[i]){
            v[i] = true, i = nx[i], sc++;
        }
        r += (sc + 1) / 2;
    }
    cout << r << endl;
}

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