Submission #391688

#	Time	Username	Problem	Language	Result	Execution time	Memory
391688		Victor	Love Polygon (BOI18_polygon)	C++17	100 / 100	309 ms	46188 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, vis;

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 si;
void dfs(string person) {
    if (vis.count(person)) return;
    vis.insert(person);
    ++si;
    if(out.count(out[person]))
    dfs(out[person]);
}

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

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

    trav(person,out){
        si=0;
        dfs(person.first);
        ans+=(si+1)>>1;
    }

    cout << ans << endl;
}

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