Submission #1116815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116815		byebye75	Mergers (JOI19_mergers)	C++14	0 / 100	54 ms	1616 KiB

mergers

#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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30