oj.uz

Submission #877102

# Submission time Handle Problem Language Result Execution time Memory
877102 2023-11-22T21:44:13 Z LucaLucaM Love Polygon (BOI18_polygon) C++17
21 / 100
 395 ms 31468 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#warning That's the baby, that's not my baby

typedef long long ll;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;

  std::vector<std::pair<std::string, std::string>> eeee(n);
  std::vector<std::string> norm;

  for (auto &[x, y] : eeee) {
    std::cin >> x >> y;
    norm.push_back(x);
    norm.push_back(y);
  }

  std::sort(norm.begin(), norm.end());
  norm.erase(std::unique(norm.begin(), norm.end()), norm.end());

  if (n & 1) {
    std::cout << -1;
    return 0;
  }

  std::function<int(int*)> brute = [&] (int *where) -> int {

    int dp[1 << n];
    for (int i = 0; i < (1 << n); i++) {
      dp[i] = INT_MAX;
    }
    dp[0] = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
      if (dp[mask] == INT_MAX) {
        continue;
      }
      for (int i = 0; i < n; i++) {
        if (!(mask & (1 << i))) {
          for (int j = 0; j < n; j++) {
            if (i != j && !(mask & (1 << j))) {
              int cost = (where[i] != j) + (where[j] != i);
              dp[mask | (1 << i) | (1 << j)] = std::min(dp[mask | (1 << i) | (1 << j)], dp[mask] + cost);
            }
          }
        }
      }
    }

    return dp[(1 << n) - 1];
  };

  int where[n] = {};

  for (auto &[x, y] : eeee) {
    int X = std::lower_bound(norm.begin(), norm.end(), x) - norm.begin() ;
    int Y = std::lower_bound(norm.begin(), norm.end(), y) - norm.begin();
    where[X] = Y;
  }

  if (n <= 20) {
    std::cout << brute(where) << ' ';
#ifndef LOCAL
    return 0;
#endif // LOCAL
  } else {
#ifdef LOCAL
    std::cout << brute(where) << ' ';
#endif // LOCAL
  }

  int inDeg[n] = {};
  for (int i = 0; i < n; i++) {
    inDeg[where[i]]++;
  }

  bool Issubtask2 = true;

  for (int i = 0; i < n && Issubtask2; i++) {
    if (!inDeg[i]) {
      Issubtask2 = false;
    }
  }

  std::function<int()> subtask2 = [&] () -> int {
    bool vis[n] = {};
    int odd = 0;
    int ret = 0;
    for (int i = 0; i < n; i++) {
      if (!vis[i]) {
        int len = 0;
        int j = i;
        while (!vis[j]) {
          len++;
          vis[j] = true;
          j = where[j];
        }
        assert(i == j);
        ret += (len + 1) / 2;
      }
    }
    for (int i = 0; i < n; i++) {
      assert(vis[i]);
    }
    return ret;
  };

  if (Issubtask2) {
    std::cout << subtask2();
  } else {
    assert(false);
  }

  return 0;
}

/**


10
1 2
2 3
3 1
4 4
5 5
6 6
7 8
8 9
9 10
10 7

4
1 2
2 3
3 1
4 4

4
1 2
2 3
3 4
4 1

6
1 1
2 1
3 2
4 1
5 1
6 1

**/

Compilation message

polygon.cpp:8:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    8 | #warning That's the baby, that's not my baby
      |  ^~~~~~~
polygon.cpp: In lambda function:
polygon.cpp:97:9: warning: unused variable 'odd' [-Wunused-variable]
   97 |     int odd = 0;
      |         ^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 4688 KB Output is correct
2 Correct 360 ms 4536 KB Output is correct
3 Correct 363 ms 4532 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 364 ms 4536 KB Output is correct
8 Correct 361 ms 4540 KB Output is correct
9 Correct 395 ms 4444 KB Output is correct
10 Correct 363 ms 4536 KB Output is correct
11 Correct 386 ms 4444 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 99 ms 17360 KB Output is correct
5 Incorrect 103 ms 16936 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 112 ms 31468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 4688 KB Output is correct
2 Correct 360 ms 4536 KB Output is correct
3 Correct 363 ms 4532 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 364 ms 4536 KB Output is correct
8 Correct 361 ms 4540 KB Output is correct
9 Correct 395 ms 4444 KB Output is correct
10 Correct 363 ms 4536 KB Output is correct
11 Correct 386 ms 4444 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 99 ms 17360 KB Output is correct
20 Incorrect 103 ms 16936 KB Output isn't correct
21 Halted 0 ms 0 KB -