Submission #52433

#	Time	Username	Problem	Language	Result	Execution time	Memory
52433		EntityIT	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	857 ms	180044 KiB

usmjeri

#include<bits/stdc++.h>

using namespace std;

#define int long long
typedef pair<int, int> ii;

const int N = 3 * 1e5 + 5, LOG = 19, mod = 1e9 + 7;
int n, m, plca[N][LOG], h[N], down[N], lab[N];
vector<int> gr[N];
vector<ii> adj[N];

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

void init(int u, int p) {
    plca[u][0] = p;
    for (auto v : gr[u]) if (v != p) {
        h[v] = h[u] + 1;
        init(v, u);
    }
    down[u] = h[u];
}


void prepare() {
    for (int j = 1; j < LOG; ++j) {
        for (int i = 1; i <= n; ++i){
            plca[i][j] = plca[ plca[i][j - 1] ][j - 1];
        }
    }
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    int diff = h[u] - h[v];
    for (int i = LOG - 1; i >= 0; --i) {
        if ( (diff >> i) & 1) u = plca[u][i];
    }
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; --i) {
        if (plca[u][i] != plca[v][i]) {
            u = plca[u][i]; v = plca[v][i];
        }
    }
    return plca[u][0];
}

void add_edge(int a, int b, int c) {
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
}

int fin (int u, int diff) {
    for (int i = LOG - 1; i >= 0; --i) {
        if ( (diff >> i) & 1) u = plca[u][i];
    }
    return u;
}

int process(int u, int p) {
    for (int v : gr[u]) if (v != p) {
        int rem = process(v, u);
        down[u] = min (down[u], rem);
    }
    if (down[u] < h[u]) add_edge(fin (u, h[u] - down[u]) , u, 0);
    return down[u];
}

bool check (int u, int sta) {
    if (lab[u] != -1) return lab[u] == sta;
    lab[u] = sta;
    for (auto v : adj[u]) {
        if (!check (v.first, sta ^ v.second)) return 0;
    }
    return 1;
}

int solve () {
    memset(lab, -1, sizeof lab);
    while (m--) {
        int u, v; cin >> u >> v;
        int LCA = lca (u, v);
        down[u] = min (down[u], h[LCA] + 1);
        down[v] = min (down[v], h[LCA] + 1);
        if (LCA != u && LCA != v) add_edge(u, v, 1);
    }
    int ans = 1;
    process(1, 0);
    for (int i = 2; i <= n; ++i) {
        if (lab[i] == -1) {
            if (!check (i, 0)) return 0;
            ans = (ans * 2) % mod;
        }
    }
    return ans;
}

signed main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    init(1, 0);
    prepare();
    cout << solve();
    return 0;
}
/*
4 1
1 2
2 3
3 4
2 4
answer: 4;
*/

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