oj.uz

Submission #1116813

# Submission time Handle Problem Language Result Execution time Memory
1116813 2024-11-22T12:21:39 Z byebye75 Mergers (JOI19_mergers) C++14
0 / 100
 35 ms 27592 KB 
#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.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20936 KB Output is correct
2 Incorrect 35 ms 27592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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