Submission #1277279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277279		hotaruu	Usmjeri (COCI17_usmjeri)	C++20	28 / 140	192 ms	80672 KiB

usmjeri

#include <bits/stdc++.h>
using namespace std;

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

int n, m;
vector<int> g[MAXN];
int up[MAXN][20], depth[MAXN];
int high[MAXN];
int color[MAXN];
vector<pair<int,int>> logic[MAXN]; // đồ thị logic (u,v, parity)

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

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a,b);
    int k = depth[a] - depth[b];
    for (int i = 19; i >= 0; i--)
        if (k >> i & 1) 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];
}

// --- Tính high[] ---
void add_path(int a, int b) {
    int c = lca(a, b);
    high[a]++;
    high[b]++;
    high[c] -= 2;
}

// --- Duyệt cộng dồn high và xây đồ thị logic ---
void connect(int u, int p) {
    for (int v : g[u]) if (v != p) {
        connect(v, u);
        if (high[v] > 0) {
            // Có ràng buộc hướng qua nhánh v-u
            logic[v].push_back({u, 0});
            logic[u].push_back({v, 0});
        }
        high[u] += high[v];
    }
}

// --- DFS kiểm tra mâu thuẫn 2-color ---
bool dfs_color(int u, int c) {
    color[u] = c;
    for (auto [v, w] : logic[u]) {
        int nc = c ^ w;
        if (color[v] == -1) {
            if (!dfs_color(v, nc)) return false;
        } else if (color[v] != nc) return false;
    }
    return true;
}

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

    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs_lca(1, 0);

    vector<pair<int,int>> pairs;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        pairs.push_back({a, b});
        add_path(a, b);
    }

    connect(1, 0);

    // Thêm các ràng buộc logic khác nếu có
    // (ví dụ nếu LCA khác a,b thì thêm (a,b,1))

    long long ans = 1;
    memset(color, -1, sizeof(color));

    for (int i = 1; i <= n; i++) if (color[i] == -1) {
        if (!dfs_color(i, 0)) {
            cout << 0;
            return 0;
        }
        ans = (ans * 2) % MOD;
    }

    cout << ans << "\n";
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 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