oj.uz

Submission #855998

# Submission time Handle Problem Language Result Execution time Memory
855998 2023-10-02T14:01:42 Z RiverFlow Love Polygon (BOI18_polygon) C++14
21 / 100
 133 ms 88840 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], vis[N];

void main_code() {
    cin >> n; map<string, int> mp;
    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;
            }
            res += (cnt + 1) / 2;
        }
        cout << res;
        return ;
    }
}


/*     Let the river flows naturally     */

Compilation message

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 20 ms 88668 KB Output is correct
2 Correct 21 ms 88668 KB Output is correct
3 Correct 21 ms 88700 KB Output is correct
4 Correct 10 ms 88676 KB Output is correct
5 Correct 10 ms 88668 KB Output is correct
6 Correct 15 ms 88668 KB Output is correct
7 Correct 19 ms 88700 KB Output is correct
8 Correct 21 ms 88704 KB Output is correct
9 Correct 20 ms 88668 KB Output is correct
10 Correct 26 ms 88668 KB Output is correct
11 Correct 23 ms 88696 KB Output is correct
12 Correct 10 ms 88668 KB Output is correct
13 Correct 10 ms 88840 KB Output is correct
14 Correct 10 ms 88668 KB Output is correct
15 Correct 10 ms 88540 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 88668 KB Output is correct
2 Correct 10 ms 88596 KB Output is correct
3 Correct 10 ms 88668 KB Output is correct
4 Correct 133 ms 12308 KB Output is correct
5 Incorrect 127 ms 14472 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 88668 KB Output is correct
2 Correct 21 ms 88668 KB Output is correct
3 Correct 21 ms 88700 KB Output is correct
4 Correct 10 ms 88676 KB Output is correct
5 Correct 10 ms 88668 KB Output is correct
6 Correct 15 ms 88668 KB Output is correct
7 Correct 19 ms 88700 KB Output is correct
8 Correct 21 ms 88704 KB Output is correct
9 Correct 20 ms 88668 KB Output is correct
10 Correct 26 ms 88668 KB Output is correct
11 Correct 23 ms 88696 KB Output is correct
12 Correct 10 ms 88668 KB Output is correct
13 Correct 10 ms 88840 KB Output is correct
14 Correct 10 ms 88668 KB Output is correct
15 Correct 10 ms 88540 KB Output is correct
16 Correct 10 ms 88668 KB Output is correct
17 Correct 10 ms 88596 KB Output is correct
18 Correct 10 ms 88668 KB Output is correct
19 Correct 133 ms 12308 KB Output is correct
20 Incorrect 127 ms 14472 KB Output isn't correct
21 Halted 0 ms 0 KB -