oj.uz

Submission #1114498

# Submission time Handle Problem Language Result Execution time Memory
1114498 2024-11-19T06:23:13 Z vjudge1 Newspapers (CEOI21_newspapers) C++17
4 / 100
 2 ms 592 KB 
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(1000) + 5;

int N, M;
std::vector<int> adj[max_N], cdj[max_N];

std::vector<int> stk;
int tin[max_N], low[max_N], belong[max_N], siz[max_N], timer, nc;
void dfs1(int v, int pr) {
    stk.emplace_back(v);
    low[v] = tin[v] = ++timer;
    for (auto u : adj[v]) {
        if (u == pr) {
            continue;
        }
        if (low[u] == 0) {
            dfs1(u, v);
            low[v] = std::min(low[v], low[u]);
        } else if (belong[u] == 0) {
            low[v] = std::min(low[v], tin[u]);
        }
    }
    if (low[v] == tin[v]) {
        ++nc;
        int u;
        do {
            u = stk.back();
            stk.pop_back();
            belong[u] = nc;
            ++siz[nc - 1];
        } while (u != v);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int A, B;
        std::cin >> A >> B;
        --A, --B;
        adj[A].emplace_back(B);
        adj[B].emplace_back(A);
    }

    dfs1(0, 0);

    if (nc != N) {
        std::cout << "NO\n";
        return 0;
    }

    for (int i = 0; i < N; ++i) {
        if (adj[i].size() == M) {
            std::cout << "YES\n";
            std::cout << "2\n";
            std::cout << i + 1 << ' ' << i + 1 << '\n';
            return 0;
        }
    }

    std::cout << "YES\n1\n1\n";

    return 0;
}

Compilation message

newspapers.cpp: In function 'int main()':
newspapers.cpp:65:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |         if (adj[i].size() == M) {
      |             ~~~~~~~~~~~~~~^~~~

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Provide a successful but not optimal strategy.
2 Correct 1 ms 336 KB Output is correct
3 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
4 Partially correct 1 ms 512 KB Failed to provide a successful strategy.
5 Correct 1 ms 336 KB Output is correct
6 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
7 Correct 1 ms 336 KB Output is correct
8 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
4.0 / 8.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Provide a successful but not optimal strategy.
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
5 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
6 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
7 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
8 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
9 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
10 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
11 Partially correct 1 ms 592 KB Failed to provide a successful strategy.
12 Partially correct 1 ms 592 KB Failed to provide a successful strategy.
13 Partially correct 1 ms 592 KB Failed to provide a successful strategy.
14 Partially correct 1 ms 592 KB Failed to provide a successful strategy.
15 Partially correct 1 ms 592 KB Failed to provide a successful strategy.
16 Partially correct 1 ms 592 KB Failed to provide a successful strategy.
17 Partially correct 2 ms 592 KB Failed to provide a successful strategy.
18 Partially correct 2 ms 592 KB Failed to provide a successful strategy.
19 Partially correct 1 ms 592 KB Failed to provide a successful strategy.
20 Partially correct 1 ms 512 KB Failed to provide a successful strategy.

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Provide a successful but not optimal strategy.
2 Correct 1 ms 336 KB Output is correct
3 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
4 Partially correct 1 ms 512 KB Failed to provide a successful strategy.
5 Correct 1 ms 336 KB Output is correct
6 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
7 Correct 1 ms 336 KB Output is correct
8 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
9 Incorrect 1 ms 336 KB Output isn't correct
10 Halted 0 ms 0 KB -