oj.uz

Submission #1087524

# Submission time Handle Problem Language Result Execution time Memory
1087524 2024-09-12T20:24:17 Z imaxblue Party (POI11_imp) C++17
9 / 100
 1328 ms 33540 KB 
#include <iostream>
#include <vector>
#include <bitset>

const int MAX_N = 3000;

int main() {
    int n, m;
    std::cin >> n >> m;
    int k = n / 3;

    std::vector<std::bitset<MAX_N>> adj(n);

    for (int i = 0; i < m; ++i) {
        int a_i, b_i;
        std::cin >> a_i >> b_i;
        --a_i; --b_i; // Zero-based indexing
        adj[a_i].set(b_i);
        adj[b_i].set(a_i);
    }

    for (int u = 0; u < n; ++u) {
        std::bitset<MAX_N> S;
        S.set(u);
        std::bitset<MAX_N> Candidates = adj[u];

        while (S.count() < k && Candidates.any()) {
            int v = -1;
            // Find a candidate v
            for (int i = Candidates._Find_first(); i < n; i = Candidates._Find_next(i)) {
                if ((adj[i] & S) == S) {
                    v = i;
                    break;
                }
            }
            if (v == -1) break;
            S.set(v);
            Candidates &= adj[v];
            Candidates.reset(v);
        }

        if (S.count() >= k) {
            // Output the clique
            for (int i = 0, cnt = 0; i < n && cnt < k; ++i) {
                if (S.test(i)) {
                    std::cout << (i + 1) << ' ';
                    ++cnt;
                }
            }
            std::cout << '\n';
            return 0;
        }
    }

    // If no clique is found (which is unlikely given the problem constraints), output an empty list.
    // However, the problem guarantees the existence of such a clique.
    return 0;
}

Compilation message

imp.cpp: In function 'int main()':
imp.cpp:27:26: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |         while (S.count() < k && Candidates.any()) {
      |                ~~~~~~~~~~^~~
imp.cpp:42:23: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |         if (S.count() >= k) {
      |             ~~~~~~~~~~^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 448 KB Output is correct
2 Incorrect 33 ms 1116 KB Wypisano za ma³o osób
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 860 KB Output is correct
2 Incorrect 139 ms 3732 KB Wypisano za ma³o osób
3 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1536 KB Output is correct
2 Incorrect 313 ms 8260 KB Wypisano za ma³o osób
3 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2644 KB Output is correct
2 Incorrect 488 ms 11952 KB Wypisano za ma³o osób
3 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 7500 KB Output is correct
2 Incorrect 587 ms 14724 KB Wypisano za ma³o osób
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 13212 KB Output is correct
2 Incorrect 802 ms 19536 KB Wypisano za ma³o osób
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 17232 KB Output is correct
2 Incorrect 899 ms 23104 KB Wypisano za ma³o osób
3 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 20416 KB Output is correct
2 Incorrect 1120 ms 26964 KB Wypisano za ma³o osób
3 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 23688 KB Output is correct
2 Incorrect 1224 ms 31060 KB Wypisano za ma³o osób
3 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 29520 KB Output is correct
2 Incorrect 1328 ms 33540 KB Wypisano za ma³o osób
3 Halted 0 ms 0 KB -