Submission #1282948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282948		asedre	Logičari (COCI21_logicari)	C++20	10 / 110	23 ms	5768 KiB

Main

// written by Asedre
#include <iostream>
#include <cmath>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <queue>
#include <numeric>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <cstring>
#include <unordered_map>
#define pb push_back
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define ull unsigned long long
using namespace std;

const int maxv = 2e5 + 3, maxn = 1e6 + 12, LOG = 25;
const int inf = 2e9;
const int MOD = 1e9 + 7, MOD2 = 1338519349;
const double PI = 3.14159265359;
//prime nums: 9059, 5419, 3571
void teztez( ) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}/*
ll binpow(ll x, ll p, ll mod) {
    if (!p) return 1;
    if (p % 2) return (x % mod * binpow(x, p - 1, mod)) % mod;
    ll xx = binpow(x, p / 2, mod);
    return (xx % mod * xx % mod) % mod;
}
*/
ll binpow(ll x, ll p) {
    if (!p) return 1;
    if (p % 2) return (x % MOD * binpow(x, p - 1) % MOD) % MOD;
    ll xx = binpow(x, p / 2) % MOD;
    return (xx * xx) % MOD;
}
ll gcd(ll a,ll b) {
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return abs(a * b) / gcd(a, b);
}
vector <int> g[maxv];

void solve( ) {
    int n; cin >> n;
    for (int i = 1; i <= n; i ++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    
    int ans = inf;
    for (int mask = 0; mask < (1 << n); mask ++) {
        bool bad = false;
        for (int i = 0; i < n; i ++) {
            int cnt = 0;
            for (auto to : g[i]) {
                if (mask & (1 << to)) cnt++;
            }
            if (cnt != 1) {
                bad = true;
                break;
            }
        }
        if (bad) continue;
        
        ans = min(ans, __builtin_popcount(mask));
    }
    
    cout << (ans == inf ? -1 : ans) << "\n";
}
signed main( ) {
    teztez( );
    //freopen("angle2.in", "r", stdin); freopen("angle2.out", "w", stdout);
    int testcases = 1;
    //cin >> testcases;
    while (testcases--) {
        solve( );
    }
    return 0;
}

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