oj.uz

Submission #52433

# Submission time Handle Problem Language Result Execution time Memory
52433 2018-06-26T01:48:33 Z EntityIT Usmjeri (COCI17_usmjeri) C++14
140 / 140
 857 ms 180044 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 45936 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 101756 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 101756 KB Output is correct
2 Correct 17 ms 101756 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 101756 KB Output is correct
2 Correct 17 ms 101756 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 101756 KB Output is correct
2 Correct 20 ms 101756 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 101756 KB Output is correct
2 Correct 19 ms 101756 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 101756 KB Output is correct
2 Correct 597 ms 111724 KB Output is correct
3 Correct 385 ms 111724 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 856 ms 128984 KB Output is correct
2 Correct 857 ms 136916 KB Output is correct
3 Correct 508 ms 136916 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 150428 KB Output is correct
2 Correct 544 ms 150428 KB Output is correct
3 Correct 452 ms 150428 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 171220 KB Output is correct
2 Correct 575 ms 180044 KB Output is correct
3 Correct 369 ms 180044 KB Output is correct