Submission #1277283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277283		hotaruu	Usmjeri (COCI17_usmjeri)	C++20	0 / 140	238 ms	70740 KiB

usmjeri

#include <iostream>
#include <vector>
#include <algorithm>

// Constants for array sizes and modulo operation
const int MAXN = 300005;
const int LOGN = 19;
const int MOD = 1e9 + 7;

// Adjacency list for the input tree
std::vector<int> adj[MAXN];
// Parent table for LCA binary lifting and depth of each node
int parent[MAXN][LOGN];
int depth[MAXN];
int n, m;

// Difference array to mark constrained paths
int up_sum[MAXN];
// Adjacency list for the logic graph. Stores {neighbor, constraint_type}
// constraint_type = 0 means same color, 1 means different color.
std::vector<std::pair<int, int>> logic_adj[MAXN];

// Array to store the color (0 or 1) of each node in the logic graph
int color[MAXN];

// Standard DFS to build the parent table and calculate depths
void dfs_tree(int u, int p, int d) {
    depth[u] = d;
    parent[u][0] = p;
    for (int v : adj[u]) {
        if (v != p) {
            dfs_tree(v, u, d + 1);
        }
    }
}

// Precomputes the parent table for fast LCA queries
void preprocess_lca() {
    for (int j = 1; j < LOGN; ++j) {
        for (int i = 1; i <= n; ++i) {
            if (parent[i][j - 1] != 0) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }
        }
    }
}

// Finds the Lowest Common Ancestor of nodes u and v
int lca(int u, int v) {
    if (depth[u] < depth[v]) std::swap(u, v);
    for (int j = LOGN - 1; j >= 0; --j) {
        if (depth[u] - (1 << j) >= depth[v]) {
            u = parent[u][j];
        }
    }
    if (u == v) return u;
    for (int j = LOGN - 1; j >= 0; --j) {
        if (parent[u][j] != 0 && parent[u][j] != parent[v][j]) {
            u = parent[u][j];
            v = parent[v][j];
        }
    }
    return parent[u][0];
}

// DFS to compute sums from the difference array
void dfs_sum(int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            dfs_sum(v, u);
            up_sum[u] += up_sum[v];
        }
    }
}

// BFS to 2-color a component of the logic graph
bool bfs_color(int start_node) {
    std::vector<int> q;
    q.push_back(start_node);
    color[start_node] = 0;
    
    int head = 0;
    while(head < q.size()){
        int u = q[head++];
        
        for (auto& edge : logic_adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            int required_color = (color[u] + weight) % 2;

            if (color[v] == -1) {
                color[v] = required_color;
                q.push_back(v);
            } else if (color[v] != required_color) {
                return false; // Contradiction found
            }
        }
    }
    return true;
}


int main() {
    // Fast I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 1. Read input and build tree
    std::cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 2. Preprocess for LCA
    dfs_tree(1, 0, 0);
    preprocess_lca();

    // 3. Process M queries and update logic graph and difference array
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        int l = lca(u, v);

        // Add 'different color' constraint
        logic_adj[u].push_back({v, 1});
        logic_adj[v].push_back({u, 1});

        // Mark paths for 'same color' constraint propagation
        up_sum[u]++;
        up_sum[v]++;
        up_sum[l] -= 2;
    }

    // 4. Build 'same color' constraints using the processed difference array
    dfs_sum(1, 0);
    for (int i = 1; i <= n; ++i) {
        if (up_sum[i] > 0 && parent[i][0] != 0) {
            logic_adj[i].push_back({parent[i][0], 0});
            logic_adj[parent[i][0]].push_back({i, 0});
        }
    }

    // 5. 2-Color the logic graph and calculate the result
    for(int i = 1; i <= n; ++i) {
        color[i] = -1;
    }

    long long result = 1;
    for (int i = 1; i <= n; ++i) {
        if (color[i] == -1) {
            if (!bfs_color(i)) {
                result = 0; // Impossible to satisfy constraints
                break;
            }
            // Each new independent component doubles the number of solutions
            result = (result * 2) % MOD;
        }
    }

    std::cout << result << std::endl;

    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14