제출 #1261712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261712		anteknne	Love Polygon (BOI18_polygon)	C++20	0 / 100	151 ms	14232 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[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];
        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 (ok) {
                cnt ++;
                continue;
            }
            wyn ++;
        }
    }



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



    return 0;
}

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