oj.uz

Submission #525936

# Submission time Handle Problem Language Result Execution time Memory
525936 2022-02-13T08:58:35 Z Slavita Logičari (COCI21_logicari) C++14
10 / 110
 332 ms 11492 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{
        assert(0);
        if (n == 1){
            cout << 0;
        }else if (n == 2){
            cout << 1;
        } else cout << n - 2;
    }

    return 0;
}
/*
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 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 Runtime error 66 ms 11492 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 2636 KB Output is correct
2 Correct 306 ms 2636 KB Output is correct
3 Correct 269 ms 2636 KB Output is correct
4 Correct 332 ms 2640 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 136 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 65 ms 2636 KB Output is correct
9 Correct 238 ms 2636 KB Output is correct
10 Correct 231 ms 2636 KB Output is correct
11 Correct 35 ms 2636 KB Output is correct
12 Correct 291 ms 2636 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 2636 KB Output is correct
2 Correct 306 ms 2636 KB Output is correct
3 Correct 269 ms 2636 KB Output is correct
4 Correct 332 ms 2640 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 136 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 65 ms 2636 KB Output is correct
9 Correct 238 ms 2636 KB Output is correct
10 Correct 231 ms 2636 KB Output is correct
11 Correct 35 ms 2636 KB Output is correct
12 Correct 291 ms 2636 KB Output is correct
13 Runtime error 5 ms 5196 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 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 Runtime error 66 ms 11492 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -