Submission #1261724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261724		anteknne	Love Polygon (BOI18_polygon)	C++20	29 / 100	155 ms	14508 KiB

polygon

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 100 * 1000 + 17;
map<string, int> m;
vector<int> graf[MAXN];
bool uzyte[MAXN];
deque<int> d;
int deg[MAXN];

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    string s, t;
    int cnt = 0;
    for (int i = 0; i < n; i ++) {
        cin >> s >> t;
        if (m[s] == 0) {
            cnt ++;
            m[s] = cnt;
        }
        if (m[t] == 0) {
            cnt ++;
            m[t] = cnt;
        }
        graf[m[s]].pb(m[t]);
        deg[m[t]] ++;
    }

    if (n % 2 == 1) {
        cout << -1 << "\n";
        return 0;
    }

    for (int i = 1; i <= n; i ++) {
        if (i == graf[i][0]) {
            continue;
        }
        if (i == graf[graf[i][0]][0]) {
            uzyte[graf[i][0]] = true;
            uzyte[i] = true;
        }
    }

    int wyn = 0;
    for (int i = 1; i <= n; i ++) {
        if (deg[i] == 0) {
            d.pb(i);
        }
    }

    while (!d.empty()) {
        int v = d.front();
        d.pop_front();
        int o = graf[v][0];

        if (uzyte[v] || uzyte[o]) {
            continue;
        }

        wyn ++;
        uzyte[v] = true;
        uzyte[o] = true;
        for (auto x : graf[o]) {
            deg[x] --;
            if (deg[x] == 0) {
                d.pb(x);
            }
        }
    }

    cnt = 0;
    for (int i = 1; i <= n; i ++) {
        if (!uzyte[i]) {
            bool ok = true;
            if (uzyte[graf[i][0]]) {
                ok = false;
            }
            if (graf[i][0] == i) {
                ok = false;
            }
            if (ok) {
                cnt ++;
                continue;
            }
            wyn ++;
        }
    }



    cout << wyn + cnt/2 << "\n";



    return 0;
}

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