oj.uz

답안 #855999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
855999 2023-10-02T14:03:13 Z RiverFlow Love Polygon (BOI18_polygon) C++14
21 / 100
 132 ms 88920 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;
            }
            if (cnt == 2) continue ;
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 88668 KB Output is correct
2 Correct 20 ms 88580 KB Output is correct
3 Correct 20 ms 88700 KB Output is correct
4 Correct 10 ms 88668 KB Output is correct
5 Correct 10 ms 88544 KB Output is correct
6 Correct 15 ms 88668 KB Output is correct
7 Correct 20 ms 88668 KB Output is correct
8 Correct 20 ms 88668 KB Output is correct
9 Correct 20 ms 88668 KB Output is correct
10 Correct 19 ms 88664 KB Output is correct
11 Correct 20 ms 88668 KB Output is correct
12 Correct 10 ms 88664 KB Output is correct
13 Correct 10 ms 88920 KB Output is correct
14 Correct 10 ms 88668 KB Output is correct
15 Correct 10 ms 88628 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 88920 KB Output is correct
2 Correct 10 ms 88668 KB Output is correct
3 Correct 10 ms 88596 KB Output is correct
4 Correct 132 ms 12532 KB Output is correct
5 Correct 131 ms 12368 KB Output is correct
6 Correct 124 ms 14672 KB Output is correct
7 Incorrect 123 ms 14676 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 131 ms 12364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 88668 KB Output is correct
2 Correct 20 ms 88580 KB Output is correct
3 Correct 20 ms 88700 KB Output is correct
4 Correct 10 ms 88668 KB Output is correct
5 Correct 10 ms 88544 KB Output is correct
6 Correct 15 ms 88668 KB Output is correct
7 Correct 20 ms 88668 KB Output is correct
8 Correct 20 ms 88668 KB Output is correct
9 Correct 20 ms 88668 KB Output is correct
10 Correct 19 ms 88664 KB Output is correct
11 Correct 20 ms 88668 KB Output is correct
12 Correct 10 ms 88664 KB Output is correct
13 Correct 10 ms 88920 KB Output is correct
14 Correct 10 ms 88668 KB Output is correct
15 Correct 10 ms 88628 KB Output is correct
16 Correct 10 ms 88920 KB Output is correct
17 Correct 10 ms 88668 KB Output is correct
18 Correct 10 ms 88596 KB Output is correct
19 Correct 132 ms 12532 KB Output is correct
20 Correct 131 ms 12368 KB Output is correct
21 Correct 124 ms 14672 KB Output is correct
22 Incorrect 123 ms 14676 KB Output isn't correct
23 Halted 0 ms 0 KB -