제출 #391684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391684		Victor	Love Polygon (BOI18_polygon)	C++17	29 / 100	324 ms	33672 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define per(i, a, b) for (int i = b - 1; i >= a; --i)
#define trav(a, x) for (auto& a : x)
#define sz(a) a.size()
#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

umap<string, string> out;
umap<string, int> in;
uset<string> unloved;

int ans = 0, n;

void remove(string name) {
    if (in.count(out[name]) && 1 == in[out[name]]--) unloved.insert(out[name]);
    out.erase(name);
    in.erase(name);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    if (n & 1) {
        cout << -1 << endl;
        return 0;
    }

    string n1, n2;
    vector<string>arr(n*2);
    rep(i, 0, n) {
        cin >> arr[i] >> arr[i + n];
        out.emplace(arr[i], arr[i + n]);
        in.emplace(arr[i],0);
    }

    cout<<endl;
    vector<string> rem;
    rep(i, 0, n) {
        n1 = arr[i];
        n2 = arr[i + n];
        if(n1==n2)continue;
        if (out[n2] == n1) rem.push_back(n1);
        ++in[n2];
    }

    trav(name, rem) {
        out.erase(name);
        in.erase(name);
    }

    trav(person,in)if(!person.second)unloved.insert(person.first);

    while (!unloved.empty()) {
        string name = *unloved.begin();
        unloved.erase(unloved.begin());

        if (!out.count(name) || !out.count(out[name])) continue;

        ++ans;
        remove(out[name]);
        out.erase(name);
        in.erase(name);
    }
    
    cout << ans+sz(in) << endl;
}

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