제출 #1116813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116813		byebye75	Mergers (JOI19_mergers)	C++14	0 / 100	35 ms	27592 KiB

mergers

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_N = 500000;

vector<int> tree[MAX_N];
int state[MAX_N];
int color[MAX_N];
bool visited[MAX_N];
bool conflict_state[MAX_N];

void dfs(int u, int c) {
    visited[u] = true;
    color[u] = c;
    for (int v : tree[u]) {
        if (!visited[v]) {
            dfs(v, c ^ 1);
        }
    }
}

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

    int N, K;
    cin >> N >> K;

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

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

    // Initialize
    fill(visited, visited + N, false);

    // Perform DFS to color the tree
    dfs(0, 0);

    // Map each state to the colors of its cities
    vector<int> state_colors[K];
    for (int i = 0; i < N; ++i) {
        state_colors[state[i]].push_back(color[i]);
    }

    // Check for conflicts in each state
    int conflicts = 0;
    for (int i = 0; i < K; ++i) {
        bool has_color[2] = {false, false};
        for (int c : state_colors[i]) {
            has_color[c] = true;
        }
        if (has_color[0] && has_color[1]) {
            conflict_state[i] = true;
            ++conflicts;
        } else {
            conflict_state[i] = false;
        }
    }

    // If there are no conflicting states, we need at least one merger to make the country not separable
    int answer;
    if (conflicts == 0) {
        answer = 1;
    } else {
        // Need to merge conflicting states to make the country not separable
        answer = 0;
    }

    cout << answer << '\n';

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30