oj.uz

Submission #525938

# Submission time Handle Problem Language Result Execution time Memory
525938 2022-02-13T09:01:30 Z Slavita Logičari (COCI21_logicari) C++14
10 / 110
 320 ms 5704 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 - 1;
    }

    return 0;
}
/*
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2616 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Incorrect 70 ms 5704 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 320 ms 2636 KB Output is correct
2 Correct 311 ms 2636 KB Output is correct
3 Correct 274 ms 2636 KB Output is correct
4 Correct 287 ms 2640 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 142 ms 2636 KB Output is correct
7 Correct 1 ms 2636 KB Output is correct
8 Correct 68 ms 2636 KB Output is correct
9 Correct 234 ms 2636 KB Output is correct
10 Correct 230 ms 2636 KB Output is correct
11 Correct 39 ms 2636 KB Output is correct
12 Correct 274 ms 2636 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 2636 KB Output is correct
2 Correct 311 ms 2636 KB Output is correct
3 Correct 274 ms 2636 KB Output is correct
4 Correct 287 ms 2640 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 142 ms 2636 KB Output is correct
7 Correct 1 ms 2636 KB Output is correct
8 Correct 68 ms 2636 KB Output is correct
9 Correct 234 ms 2636 KB Output is correct
10 Correct 230 ms 2636 KB Output is correct
11 Correct 39 ms 2636 KB Output is correct
12 Correct 274 ms 2636 KB Output is correct
13 Incorrect 3 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 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2616 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Incorrect 70 ms 5704 KB Output isn't correct
6 Halted 0 ms 0 KB -