oj.uz

Submission #880832

# Submission time Handle Problem Language Result Execution time Memory
880832 2023-11-30T06:37:03 Z vjudge1 Love Polygon (BOI18_polygon) C++17
46 / 100
 691 ms 13568 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int N = 1e5 + 10;

int n, t, cnt, ans;
bool mark[N];
vector<int> G[N];
unordered_map<string, int> mp;

void dfs(int v) {
    mark[v] = true;
    cnt++;
    int u = G[v][0];
    while (!mark[u]) cnt++, mark[u] = true, u = G[u][0];
    return;
}

void solve() {
    bool a[21][21] = {};
    int dp[(1 << n) + 10];
    memset(dp, 63, sizeof dp);
    for (int i = 0; i < n; i++) {
        string u, v;
        cin >> u >> v;
        if (mp[u] == 0) mp[u] = ++t;
        if (mp[v] == 0) mp[v] = ++t;
        a[mp[u]][mp[v]] = true;
    }
    dp[0] = 0;
    for (int mask = 1; mask < (1 << n); mask++)
        for (int lg = 0; lg < n; lg++)
            if (mask & (1 << lg))
                for (int lg1 = 0; lg1 < n; lg1++)
                    if (mask & (1 << lg1) && lg1 ^ lg)
                        dp[mask] = min(dp[mask], dp[mask ^ (1 << lg) ^ (1 << lg1)] - a[lg + 1][lg1 + 1] - a[lg1 + 1][lg + 1] + 2);
    cout << dp[(1 << n) - 1] << '\n';
}

int main() {
    ios:: sync_with_stdio(0), cin.tie(0);
    cin >> n;
    if (n & 1) return cout << "-1\n", 0;
    if (n <= 20) {
        solve();
        return 0;
    }
    for (int i = 0; i < n; i++) {
        string u, v;
        cin >> u >> v;
        if (mp[u] == 0) mp[u] = ++t;
        if (mp[v] == 0) mp[v] = ++t;
        G[mp[u]].pb(mp[v]);
    }
    for (int i = 1; i <= n; i++)
        if (!mark[i]) {
            dfs(i);
            if (cnt ^ 2) ans += (cnt + 1) / 2;
            cnt = 0;
        }
    cout << ans << '\n';
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 6992 KB Output is correct
2 Correct 668 ms 6884 KB Output is correct
3 Correct 667 ms 6880 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 680 ms 6892 KB Output is correct
8 Correct 681 ms 6888 KB Output is correct
9 Correct 689 ms 6892 KB Output is correct
10 Correct 691 ms 6904 KB Output is correct
11 Correct 672 ms 6892 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2664 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 53 ms 13512 KB Output is correct
5 Correct 54 ms 13568 KB Output is correct
6 Correct 72 ms 13420 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 13516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 6992 KB Output is correct
2 Correct 668 ms 6884 KB Output is correct
3 Correct 667 ms 6880 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 680 ms 6892 KB Output is correct
8 Correct 681 ms 6888 KB Output is correct
9 Correct 689 ms 6892 KB Output is correct
10 Correct 691 ms 6904 KB Output is correct
11 Correct 672 ms 6892 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2664 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2648 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 53 ms 13512 KB Output is correct
20 Correct 54 ms 13568 KB Output is correct
21 Correct 72 ms 13420 KB Output is correct
22 Correct 1 ms 2648 KB Output is correct
23 Incorrect 66 ms 13516 KB Output isn't correct
24 Halted 0 ms 0 KB -