Submission #1298619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298619		dzhoz0	Love Polygon (BOI18_polygon)	C++20	21 / 100	323 ms	21644 KiB

polygon

/*
    it could have been better :)
    it will next time ;)
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define INF 1e18
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>

const int MOD = 1'000'000'000 + 7;

void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    if (!name.empty())
    {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
#endif
}

// START OF DEBUG
#define db(val) "["#val" = "<<(val)<<"] "
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
// for printing std::pair
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
// for printing collection
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
// for printing std::tuple
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}
// END OF DEBUG

const int MAXN = 1e5;
int n;
int nxt[MAXN + 5];
map<string, int> mp;

namespace sub1 {

bool check() {
    return n <= 20;
}

const int N = 20;
int dp[(1 << N)];

void solve() {
    if(n & 1) {
        cout << -1 << '\n';
        return;
    }
    for(int i = 0; i < (1 << n); i++) dp[i] = INF;
    dp[0] = 0;
    for(int b = 0; b < (1 << n); b++) {
        // cout << b << ' ' << __builtin_popcount(b) << '\n';
        if(__builtin_popcount(b) % 2 == 1) continue;
        for(int i = 0; i < n; i++) {
            if(b & (1 << i)) continue;
            for(int j = 0; j < n; j++) {
                if(b & (1 << j)) continue; 
                int nb = b | (1 << i);
                nb |= (1 << j);
                int cnt = (nxt[i] != j) + (nxt[j] != i);
                dp[nb] = min(dp[nb], dp[b] + cnt);
                // cout << b << ' ' << nb << '\n';
                // cout << dp[b] << ' ' << dp[nb] << '\n';
            }
        }
    }
    if(dp[(1 << n) - 1] == INF) dp[(1 << n) - 1] = -1;
    cout << dp[(1 << n) - 1] << '\n';
}

}

void solve()
{
    cin >> n;    
    vector<pair<string, string>> v;
    vector<string> lst;
    for(int i = 1; i <= n; i++) {
        string s, t; cin >> s >> t;
        v.push_back({s, t});
        lst.push_back(s);
        lst.push_back(t);
    }
    sort(lst.begin(), lst.end());
    lst.erase(unique(lst.begin(), lst.end()), lst.end());
    for(int i = 0; i < (int)lst.size(); i++) {
        mp[lst[i]] = i;
    }
    // cout << mp << '\n';
    for(auto it : v) {
        nxt[mp[it.f]] = mp[it.s];
    }
    // for(int i = 0; i < n; i++) cout << nxt[i] << '\n';
    sub1::solve();
}
signed main()
{
    setIO();
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Compilation message (stderr)

polygon.cpp: In function 'void setIO(std::string)':
polygon.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
polygon.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 0 / 25
• Subtask 3: 0 / 29
• Subtask 4: 0 / 25