oj.uz

Submission #862427

# Submission time Handle Problem Language Result Execution time Memory
862427 2023-10-18T08:15:11 Z The_Samurai Love Polygon (BOI18_polygon) C++17
54 / 100
 313 ms 22096 KB 
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int inf = 1e9;

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, z = 0;
    cin >> n;
    if (n % 2) {
        cout << -1;
        return 0;
    }
    vector<pair<string, string>> adj(n);
    for (auto &it: adj) cin >> it.first >> it.second;
    map<string, int> mp;
    for (auto &it: adj) mp[it.first];
    for (auto &it: adj) mp[it.second];
    for (auto &it: mp) it.second = z++;
    set<pair<int, int>> st;
    vector<int> out(n), in(n);
    for (int i = 0; i < n; i++) out[mp[adj[i].first]] = mp[adj[i].second];
//    for (int i = 0; i < n; i++) cout << mp[adj[i].first] << ' ' << mp[adj[i].second] << endl;
    for (int i = 0; i < n; i++) in[out[i]]++;
//    for (int i = 0; i < n; i++) cout << in[i] << ' ';
//    cout << endl;
    auto solve = [&](vector<bool> &blocked) -> ll {
        for (int i = 0; i < n; i++) if (!blocked[i]) st.insert(make_pair(in[i], i));
        vector<bool> changed(n);
        int ans = 0;
        while (!st.empty()) {
            auto [c, u] = *st.begin(); st.erase(st.begin());
            if (u == out[u] or changed[out[u]]) continue;
            int v = out[u];
            if (u != out[v]) {
                st.erase(make_pair(in[out[v]], out[v]));
                in[out[v]]--;
                st.insert(make_pair(in[out[v]], out[v]));
                out[v] = u;
                ans++;
            }
            st.erase(make_pair(in[v], v));
            changed[u] = changed[v] = true;
        }
        return ans + count(changed.begin(), changed.end(), false) + count(blocked.begin(), blocked.end(), true);
    };
    vector<bool> blocked(n);
    ll ans = solve(blocked);
    in.assign(n, 0);
    for (int i = 0; i < n; i++) out[mp[adj[i].first]] = mp[adj[i].second];
    for (int i = 0; i < n; i++) in[out[i]]++;
    for (int i = 0; i < n; i++) if (!in[i]) blocked[i] = true;
    cout << min(ans, solve(blocked));
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 272 ms 21976 KB Output is correct
5 Correct 269 ms 21844 KB Output is correct
6 Correct 279 ms 22072 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 21980 KB Output is correct
2 Correct 286 ms 21976 KB Output is correct
3 Correct 207 ms 21984 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 313 ms 21980 KB Output is correct
6 Correct 292 ms 22096 KB Output is correct
7 Correct 294 ms 22092 KB Output is correct
8 Correct 220 ms 21972 KB Output is correct
9 Correct 215 ms 22096 KB Output is correct
10 Correct 164 ms 21972 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 448 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -