Submission #877103

#	Time	Username	Problem	Language	Result	Execution time	Memory
877103		LucaLucaM	Love Polygon (BOI18_polygon)	C++17	46 / 100	374 ms	28024 KiB

polygon

#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);
        if (len != 2) {
          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;
}

/**

2
1 2
2 1


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 (stderr)

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 / 21
• Subtask 2: 25 / 25
• Subtask 3: 0 / 29
• Subtask 4: 0 / 25