oj.uz

Submission #959179

# Submission time Handle Problem Language Result Execution time Memory
959179 2024-04-07T14:48:49 Z lalig777 Geppetto (COCI15_geppetto) C++14
80 / 80
 18 ms 428 KB 
#include <iostream>
#include <vector>
using namespace std;

int ans=0;
int n, m;
void subsets (int i, vector<vector<bool>>&proh, vector<int>&negado){
    if (i==n){
        ans++;
        return;
    }
    if (negado[i]==0){
        for (int k=0; k<n; k++){
            if (proh[i][k]==true) negado[k]++;
        }subsets(i+1, proh, negado);
        for (int k=0; k<n; k++){
            if (proh[i][k]==true) negado[k]--;
        }
    }
    subsets(i+1, proh, negado);
    return;
}

int main(){
    cin>>n>>m;
    vector<vector<bool>>proh(n, vector<bool>(n, false));
    vector<int>negado(n, 0);
    while (m--){
        int a, b;
        cin>>a>>b;
        proh[a-1][b-1]=true;
        proh[b-1][a-1]=true;
    }subsets(0, proh, negado);
    cout<<ans;
    return 0;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 18 ms 428 KB Output is correct