Submission #1309743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309743		ayuxhkumxr22	Usmjeri (COCI17_usmjeri)	C++20	0 / 140	236 ms	62056 KiB

usmjeri

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

using namespace std;

const int MAXN = 300005;
const int MOD = 1e9 + 7;

int N, M;
vector<int> adj[MAXN];
int depth[MAXN], up[MAXN][20];
int parent[MAXN]; // Original tree parent

// DSU for "Same" constraints (merging vertical paths)
// dsu[u] represents the edge (u, parent[u])
int dsu[MAXN]; 

int find(int x) {
    if (x == dsu[x]) return x;
    return dsu[x] = find(dsu[x]);
}

// Conflict Graph for "Different" constraints
vector<int> conflict_adj[MAXN];
int color[MAXN]; // 0: unvisited, 1: color A, 2: color B
bool impossible = false;

// 1. Standard LCA Preprocessing
void dfs_lca(int u, int p, int d) {
    depth[u] = d;
    up[u][0] = p;
    parent[u] = p;
    for (int i = 1; i < 20; i++) {
        up[u][i] = up[up[u][i-1]][i-1];
    }
    for (int v : adj[u]) {
        if (v != p) dfs_lca(v, u, d + 1);
    }
}

int get_lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int i = 19; i >= 0; i--) {
        if (depth[a] - (1 << i) >= depth[b]) {
            a = up[a][i];
        }
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) {
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

// 2. Merge vertical path u -> lca
// Optimization: We use DSU to skip already-merged edges.
// We merge edge u with edge parent[u].
void merge_path(int u, int lca) {
    // We want to merge all edges from u up to lca.
    // In DSU, 'u' represents edge (u, parent[u]).
    // We walk up. If u is already merged with parent, find(u) will take us higher.
    
    u = find(u); // Start from the highest representative of u's current block
    while (depth[u] > depth[lca]) {
        int p = find(parent[u]); // The edge above u
        if (p != u) {
            dsu[u] = p; // Merge u into p (u becomes child of p in DSU)
        }
        u = find(u); // Move to the new representative (higher up)
    }
}

// 3. Bipartite Coloring DFS
void dfs_color(int u, int c) {
    color[u] = c;
    for (int v : conflict_adj[u]) {
        if (color[v] == 0) {
            dfs_color(v, 3 - c); // Toggle 1 <-> 2
        } else if (color[v] == c) {
            impossible = true;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Root at 1
    dfs_lca(1, 1, 0);

    // Initialize DSU: each node u represents edge (u, parent[u])
    // Note: Node 1 has no edge above it, so dsu[1] is a dummy/root.
    for (int i = 1; i <= N; i++) dsu[i] = i;

    vector<pair<int, int>> constraints;
    
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        int lca = get_lca(a, b);
        
        // Step A: Merge Vertical Paths (SAME constraint)
        // Merge edges on A -> LCA
        merge_path(a, lca);
        // Merge edges on B -> LCA
        merge_path(b, lca);
        
        constraints.push_back({a, b});
    }

    // Step B: Build Conflict Graph (DIFF constraint)
    // Constraint is between the representative of A-side and B-side
    for (auto p : constraints) {
        int a = p.first;
        int b = p.second;
        int lca = get_lca(a, b);
        
        // If a == lca, purely vertical path, no conflict generated.
        // Otherwise, the relevant edge is the one representing the group ending at 'a'.
        // That edge-group is simply find(a).
        
        if (a != lca && b != lca) {
            int root_a = find(a);
            int root_b = find(b);
            
            // Add XOR constraint between these two groups
            conflict_adj[root_a].push_back(root_b);
            conflict_adj[root_b].push_back(root_a);
        }
    }

    // Step C: Count Components & Check Bipartite
    long long ans = 1;
    int components = 0;

    // We only care about nodes 2..N (edges). Node 1 is dummy.
    // Also, we only iterate over DSU roots to save time/logic, 
    // or just iterate all and skip visited.
    
    for (int i = 2; i <= N; i++) {
        // Only process the representative of a set
        if (dsu[i] == i && color[i] == 0) {
            components++;
            dfs_color(i, 1);
        }
    }

    if (impossible) {
        cout << 0 << endl;
    } else {
        // Answer is 2^k
        long long res = 1;
        for (int i = 0; i < components; i++) {
            res = (res * 2) % MOD;
        }
        cout << res << 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