oj.uz

Submission #331858

# Submission time Handle Problem Language Result Execution time Memory
331858 2020-11-30T13:14:23 Z ttnhuy313 Usmjeri (COCI17_usmjeri) C++14
140 / 140
 526 ms 85996 KB 
#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
typedef long long ll;
typedef long double ld;
const int N = 3e5 + 10;
const int base = 1e9 + 7;
 
int n, m, timer, tin[N], tout[N], depth[N], p[N], pr[N], up[N][25], col[N];
vector <pair <int, int> > e;
vector <int> g[N];
bool mk[N];
 
void dfs(int v, int pred = 0) {
    tin[v] = timer++;
 
    pr[v] = pred;
    up[v][0] = pred;
 
    for (int i = 1; i < 20; ++i)
        up[v][i] = up[up[v][i - 1]][i - 1];
 
    for (int to : g[v])
        if (to != pred) {
            depth[to] = depth[v] + 1;
            dfs(to, v);
        }
 
    tout[v] = timer++;
}
 
void paint(int v, int cl) {
    if (mk[v]) {
        if (col[v] != cl) {
            cout << 0;
            exit(0);
        }
        return;
    }
 
    mk[v] = 1;
    col[v] = cl;
 
    for (int to : g[v])
        paint(to, cl ^ 1);
}
 
int f(int x) { return (x == p[x]) ? x : p[x] = f(p[x]); }
 
void unite(int x, int y) { p[f(x)] = f(y); }
 
bool upper(int v, int u) { return (tin[v] < tin[u]) && (tout[v] > tout[u]); }
 
int _lca(int v, int u) {
    if (upper(v, u))
        return v;
 
    if (upper(u, v))
        return u;
 
    for (int i = 19; i >= 0; --i)
        if (!upper(up[v][i], u))
            v = up[v][i];
 
    return up[v][0];
}
 
void find(int v) {
    if (!v)
        return;
 
    if (f(v) == f(pr[v])) {
        find(pr[v]);
        pr[v] = pr[pr[v]];
    }
}
 
void path(int u, int v) {
    find(v);
    while (depth[u] < depth[pr[v]]) {
        unite(v, pr[v]);
        find(v = pr[v]);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
 
        x--; y--;
 
        g[x].push_back(y);
        g[y].push_back(x);
    }
 
    dfs(0);
 
    for (int i = 0; i < n; ++i)
        g[i].clear(), p[i] = i;
 
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        x--; y--;
 
        if (x == y)
            continue;
 
        if (tin[x] > tin[y])
            swap(x, y);
 
        if (tout[x] > tout[y]) path(x, y);
            else {
                int lca = _lca(x, y);
                path(lca, x);
                path(lca, y);
 
                e.push_back(make_pair(x, y));
            }
    }
 
    for (auto a : e) {
        int x = f(a.first);
        int y = f(a.second);
        if (x == y) {
            cout << 0;
            return 0;
        }
 
        g[x].push_back(y);
        g[y].push_back(x);
    }
 
    for (int i = 1; i < n; ++i)
        if (!mk[i])
            paint(i, 0);
 
    for (auto a : e)
        unite(a.first, a.second);
 
    set <int> s;
    s.clear();
    for (int i = 1; i < n; ++i)
        s.insert(f(i));
 
    int ans = 1;
    for (int i = 0; i < int(s.size()); ++i)
        (ans <<= 1) %= base;
 
    cout << ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 33388 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 85996 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7660 KB Output is correct
2 Correct 6 ms 7788 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7660 KB Output is correct
2 Correct 7 ms 7788 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8448 KB Output is correct
2 Correct 8 ms 8300 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8428 KB Output is correct
2 Correct 8 ms 8300 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 69216 KB Output is correct
2 Correct 442 ms 66784 KB Output is correct
3 Correct 228 ms 42092 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 72456 KB Output is correct
2 Correct 508 ms 72548 KB Output is correct
3 Correct 275 ms 40804 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 72956 KB Output is correct
2 Correct 416 ms 66916 KB Output is correct
3 Correct 274 ms 43876 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 73056 KB Output is correct
2 Correct 476 ms 72972 KB Output is correct
3 Correct 227 ms 41068 KB Output is correct