oj.uz

Submission #738430

# Submission time Handle Problem Language Result Execution time Memory
738430 2023-05-08T18:17:42 Z Olympia Logičari (COCI21_logicari) C++17
20 / 110
 149 ms 2892 KB 
#include <iostream>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <map>
#include <deque>
#include <stdio.h>
using namespace std; 
int new_max (int a, int b) {
    if (a == -1) return b;
    if (b == -1) return a;
    return max(a, b);
} 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<pair<int,int>> edges;
    int deg[N];
    for (int i = 0; i < N; i++) {
        deg[i] = 0;
    }
    for (int i = 0; i < N; i++) {
        int u, v; cin >> u >> v; --u; --v;
        edges.emplace_back(u, v);
        deg[u]++, deg[v]++;
    }
    bool s1 = true;
    for (int i = 0; i < N; i++) {
        s1 &= (deg[i] == 2);
    }
    if (s1) {
        if (N % 4 == 0) {
            cout << N/2;
        } else {
            cout << -1;
        }
        exit(0);
    }
    int lst = -1;
    for (int i = 0; i < (1 << N); i++) {
        vector<int> cnt;
        cnt.assign(N, 0);
        for (auto& p: edges) {
            if (i & (1 << p.first)) cnt[p.second]++;
            if (i & (1 << p.second)) cnt[p.first]++;
        }
        bool fine = true;
        for (int i = 0; i < cnt.size(); i++) {
            fine &= (cnt[i] == 1);
        }
        if (fine) {
            lst = new_max(lst, __builtin_popcount(i));
        }
    }
    cout << lst;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < cnt.size(); i++) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 17 ms 1832 KB Output is correct
6 Correct 21 ms 2816 KB Output is correct
7 Correct 21 ms 2772 KB Output is correct
8 Correct 20 ms 2892 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 292 KB Output is correct
2 Correct 148 ms 300 KB Output is correct
3 Correct 143 ms 296 KB Output is correct
4 Correct 149 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 70 ms 292 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 33 ms 212 KB Output is correct
9 Correct 126 ms 296 KB Output is correct
10 Correct 123 ms 292 KB Output is correct
11 Correct 19 ms 212 KB Output is correct
12 Correct 140 ms 296 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 292 KB Output is correct
2 Correct 148 ms 300 KB Output is correct
3 Correct 143 ms 296 KB Output is correct
4 Correct 149 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 70 ms 292 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 33 ms 212 KB Output is correct
9 Correct 126 ms 296 KB Output is correct
10 Correct 123 ms 292 KB Output is correct
11 Correct 19 ms 212 KB Output is correct
12 Correct 140 ms 296 KB Output is correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 17 ms 1832 KB Output is correct
6 Correct 21 ms 2816 KB Output is correct
7 Correct 21 ms 2772 KB Output is correct
8 Correct 20 ms 2892 KB Output is correct
9 Correct 145 ms 292 KB Output is correct
10 Correct 148 ms 300 KB Output is correct
11 Correct 143 ms 296 KB Output is correct
12 Correct 149 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 70 ms 292 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 33 ms 212 KB Output is correct
17 Correct 126 ms 296 KB Output is correct
18 Correct 123 ms 292 KB Output is correct
19 Correct 19 ms 212 KB Output is correct
20 Correct 140 ms 296 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -