oj.uz

Submission #856002

# Submission time Handle Problem Language Result Execution time Memory
856002 2023-10-02T14:14:42 Z RiverFlow Love Polygon (BOI18_polygon) C++14
46 / 100
 133 ms 86872 KB 
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b or a == -1) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};

int n, g[N];

int dp[21][1 << 20];

void subtask1() {
    memset(dp, -1, sizeof dp); dp[0][0] = 0;
    FOR(i, 0, n - 1)
    FOR(mask, 0, (1 << n) - 1) if (dp[i][mask] != -1) {
        if (1 & (mask >> i)) {
            mini(dp[i + 1][mask], dp[i][mask]);
            continue ;
        }
        FOR(k, 0, n - 1) if ( k != i and (1 & (mask >> k)) == 0 ) {
            mini(dp[i + 1][mask | (1 << k) | (1 << i)],
                 dp[i][mask] + (g[i + 1] != k + 1)
                             + (g[k + 1] != i + 1));
        }
    }
    cout << dp[n][ (1 << n) - 1 ];
}

int deg[N], used[N], vis[N];

void main_code() {
    cin >> n; map<string, int> mp;
    if (n % 2 == 1) evoid(-1);
    for(int i = 1, cnt = 0; i <= n; ++i) {
        string x, y; cin >> x >> y;
        if (mp.find(x) == mp.end()) {
            mp[x] = ++cnt;
        }
        if (mp.find(y) == mp.end()) {
            mp[y] = ++cnt;
        }
        int a = mp[x], b = mp[y];
        g[a] = b;
    }
    if (n <= 20)
        return subtask1(), void();
    FOR(i, 1, n) ++deg[g[i]];
    bool sub2 = 1;
    FOR(i, 1, n) sub2 &= (deg[i] == 1);
    if (sub2) {
        int res = 0;
        FOR(i, 1, n) if (vis[i] == 0) {
            int cnt = 1; vis[i] = 1;
            for(int j = g[i]; j != i; j = g[j]) {
                ++cnt; vis[j] = 1;
            }
            if (cnt == 2) continue ;
            res += (cnt + 1) / 2;
        }
        cout << res;
        return ;
    }
    queue<int> q;
    int res = 0;
    FOR(i, 1, n) {
        if (i == g[i]) {
            ++res; used[i] = 1; deg[i] == 0;
            continue ;
        }
        if (deg[i] == 0) q.push(i), used[i] = 1;
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (used[u]) {
            --deg[g[u]];
            if (deg[g[u]] == 0) {
                q.push(g[u]);
                continue ;
            }
        }
        ++res;
        used[u] = 1;
        if (used[g[u]] == 0) {
            used[g[u]] = 1;
            --deg[g[u]];
            if (deg[g[u]] == 0) q.push(g[u]);
            continue ;
        } else {
            --deg[g[u]];
            if (deg[g[u]] == 0) q.push(g[u]);
        }
    }
    cout << res;
}


/*     Let the river flows naturally     */

Compilation message

polygon.cpp: In function 'void main_code()':
polygon.cpp:105:40: warning: statement has no effect [-Wunused-value]
  105 |             ++res; used[i] = 1; deg[i] == 0;
      |                                 ~~~~~~~^~~~
polygon.cpp: In function 'int main()':
polygon.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
polygon.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 86872 KB Output is correct
2 Correct 19 ms 86616 KB Output is correct
3 Correct 20 ms 86620 KB Output is correct
4 Correct 9 ms 86620 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 21 ms 86784 KB Output is correct
8 Correct 20 ms 86764 KB Output is correct
9 Correct 20 ms 86580 KB Output is correct
10 Correct 19 ms 86620 KB Output is correct
11 Correct 20 ms 86652 KB Output is correct
12 Correct 10 ms 86616 KB Output is correct
13 Correct 9 ms 86620 KB Output is correct
14 Correct 9 ms 86620 KB Output is correct
15 Correct 10 ms 86620 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 86620 KB Output is correct
2 Correct 10 ms 86536 KB Output is correct
3 Correct 9 ms 86620 KB Output is correct
4 Correct 132 ms 10884 KB Output is correct
5 Correct 126 ms 10796 KB Output is correct
6 Correct 133 ms 10692 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 86872 KB Output is correct
2 Correct 19 ms 86616 KB Output is correct
3 Correct 20 ms 86620 KB Output is correct
4 Correct 9 ms 86620 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 21 ms 86784 KB Output is correct
8 Correct 20 ms 86764 KB Output is correct
9 Correct 20 ms 86580 KB Output is correct
10 Correct 19 ms 86620 KB Output is correct
11 Correct 20 ms 86652 KB Output is correct
12 Correct 10 ms 86616 KB Output is correct
13 Correct 9 ms 86620 KB Output is correct
14 Correct 9 ms 86620 KB Output is correct
15 Correct 10 ms 86620 KB Output is correct
16 Correct 9 ms 86620 KB Output is correct
17 Correct 10 ms 86536 KB Output is correct
18 Correct 9 ms 86620 KB Output is correct
19 Correct 132 ms 10884 KB Output is correct
20 Correct 126 ms 10796 KB Output is correct
21 Correct 133 ms 10692 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Incorrect 126 ms 10716 KB Output isn't correct
24 Halted 0 ms 0 KB -