oj.uz

Submission #525939

# Submission time Handle Problem Language Result Execution time Memory
525939 2022-02-13T09:02:04 Z Slavita Logičari (COCI21_logicari) C++14
10 / 110
 285 ms 6148 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define ve vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi pair<int,int>
#define all(v) v.begin(),v.end()
#define si(v) (int)v.size()
#define en '\n'
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_muiltiset tree<int, null_type,less_equal<>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 228;
const int big = 1e9;
const ll llbig = 1e18 + 228;
//ordered_set os; // os.order_of_key(4), (*os.find_by_order(5))
int n, m;
int mrk[N];
vector<int> g[N];

bool getbit(int x, int bit){
    assert(bit > 0);
    bit--;
    return (x & (1 << bit)) == (1 << bit);
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        int a, b; cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }

    //if (n <= 21){
        int ans = big;
        for (int mask = 1; mask <= (1 << (n + 1)); mask++){
            bool ok = 1; int an = 0;
            for (int i = 1; i <= n; i++) mrk[i] = 0;
            for (int i = 1; i <= n; i++){
                if (!getbit(mask, i)) continue;
                an++;
                mrk[i] = 2;
                for (auto u : g[i]){
                    if (getbit(mask, u)) continue;
                    if (mrk[u]) {ok = 0; break;}
                    mrk[u] = 1;
                }
            }
            for (int i = 1; i <= n; i++) {
                int kol = 0;
                for (auto u : g[i]){
                    if (getbit(mask, u)) kol++;
                }
                if (kol != 1) {ok = 0; break;}
            }
            if (ok){
                ans = min(ans, an);
            }
        }
        if (ans == big) cout << -1; else cout << ans;
    //}else{
    //    cout << n - 3;
    //}

    return 0;
}
/*
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Incorrect 67 ms 6148 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 2636 KB Output is correct
2 Correct 283 ms 2636 KB Output is correct
3 Correct 270 ms 2636 KB Output is correct
4 Correct 271 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 132 ms 2636 KB Output is correct
7 Correct 1 ms 2636 KB Output is correct
8 Correct 65 ms 2636 KB Output is correct
9 Correct 223 ms 2636 KB Output is correct
10 Correct 206 ms 2636 KB Output is correct
11 Correct 34 ms 2636 KB Output is correct
12 Correct 257 ms 2636 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 2636 KB Output is correct
2 Correct 283 ms 2636 KB Output is correct
3 Correct 270 ms 2636 KB Output is correct
4 Correct 271 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 132 ms 2636 KB Output is correct
7 Correct 1 ms 2636 KB Output is correct
8 Correct 65 ms 2636 KB Output is correct
9 Correct 223 ms 2636 KB Output is correct
10 Correct 206 ms 2636 KB Output is correct
11 Correct 34 ms 2636 KB Output is correct
12 Correct 257 ms 2636 KB Output is correct
13 Incorrect 2 ms 2636 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Incorrect 67 ms 6148 KB Output isn't correct
6 Halted 0 ms 0 KB -