oj.uz

Submission #1116815

# Submission time Handle Problem Language Result Execution time Memory
1116815 2024-11-22T12:23:11 Z byebye75 Mergers (JOI19_mergers) C++14
0 / 100
 54 ms 1616 KB 
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> Ai(N - 1), Bi(N - 1);
    for (int i = 0; i < N - 1; ++i) {
        cin >> Ai[i] >> Bi[i];
        --Ai[i]; // Convert to 0-based indexing
        --Bi[i];
    }

    vector<int> S(N);
    for (int i = 0; i < N; ++i) {
        cin >> S[i];
        --S[i]; // Convert to 0-based indexing
    }

    // Adjacency matrix for the state graph
    int adj[7][7]; // Since K <= 7
    memset(adj, 0, sizeof(adj));

    // Build the state graph
    for (int i = 0; i < N - 1; ++i) {
        int s1 = S[Ai[i]];
        int s2 = S[Bi[i]];
        if (s1 != s2) {
            adj[s1][s2] = 1;
            adj[s2][s1] = 1;
        }
    }

    // Count unique edges between states
    int E = 0;
    for (int i = 0; i < K; ++i) {
        for (int j = i + 1; j < K; ++j) {
            if (adj[i][j]) {
                ++E;
            }
        }
    }

    int N_states = K;
    int cycles = E - N_states + 1;

    // Calculate the minimum number of mergers needed
    int answer = max(0, 1 - cycles);

    cout << answer << endl;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 1616 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -