제출 #1004747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1004747		atom	Logičari (COCI21_logicari)	C++17	20 / 110	138 ms	7092 KiB

Main

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
 
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
 
const int N = 1e5 + 5;
// 1: last position of x, -1: second-last position of x -> sum(l, r) = 0-> non-unique subarray, > 0: unique

vector <int> adj[N];
int n;

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    bool sub1 = true;
    for (int i = 1; i <= n; ++i) {
        if ((int) adj[i].size() != 2) sub1 = false;
    }

    if (sub1) {
        cout << (n % 4 == 0? (n / 2) : -1) << "\n";
        return 0;
    }

    bool sub2 = (n <= 20);
    if (sub2) {
        int res = 1e9;
        for (int msk = 0; msk < (1 << n); ++msk) {
            vector <bool> b(n + 1, 0);
            int cur = 0;
            for (int i = 1; i <= n; ++i) { 
                if (msk & (1 << (i - 1))) {
                    b[i] = 1;
                    ++cur;
                }
            }

            bool ans = true;    
            for (int i = 1; i <= n; ++i) {
                int cnt = 0;
                for (int j : adj[i])
                    if (b[j])
                        ++cnt;
                if (cnt != 1) ans = false;
            }

            if (ans) {
                res = min(res, cur);
            }
        }
        cout << (res != 1e9? res : -1) << "\n";
        return 0;
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 40
• Subtask 4: 0 / 50