oj.uz

Submission #235762

# Submission time Handle Problem Language Result Execution time Memory
235762 2020-05-29T16:06:43 Z VEGAnn Usmjeri (COCI17_usmjeri) C++14
140 / 140
 667 ms 74292 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair
#define ft first
#define sd second
#define PB push_back
#define pli pair<ll,int>
using namespace std;
typedef long long ll;
const int N = 300100;
const int PW = 20;
const int oo = 2e9;
const int md = int(1e9) + 7;
vector<int> g[N], gr[N];
int n, m, pr[N], ans = 1, up[N][PW], tin[N], tout[N], tt = 0, ad[N];
int V[N], U[N], col[N];

int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x])); }

void dfs(int v, int p){
    up[v][0] = p;

    for (int po = 1; po < PW; po++)
        up[v][po] = up[up[v][po - 1]][po - 1];

    tin[v] = ++tt;

    for (int u : g[v]){
        if (p == u) continue;

        dfs(u, v);
    }

    tout[v] = tt;
}

bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a, int b){
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;

    for (int po = PW - 1; po >= 0; po--)
        if (!upper(up[a][po], b))
            a = up[a][po];

    return up[a][0];
}

int pra(int a, int b){
    for (int po = PW - 1; po >= 0; po--)
        if (!upper(up[a][po], b))
            a = up[a][po];

    return a;
}

void DFS(int v){
    for (int u : g[v]){
        if (u == up[v][0]) continue;

        DFS(u);

        ad[v] += ad[u];
    }

    if (ad[v] > 0)
        pr[get(v)] = get(up[v][0]);
}

void BAD(){
    cout << 0;
    exit(0);
}

void rec(int v, int ncl){
    if (col[v] > 0){
        if (col[v] != ncl)
            BAD();
        return;
    }

    col[v] = ncl;

    for (int u : gr[v])
        rec(u, 3 - ncl);
}

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        x--; y--;

        g[x].PB(y);
        g[y].PB(x);

        pr[i] = i;
    }

    dfs(0, 0);

    for (int i = 0; i < m; i++){
        int x, y; cin >> x >> y;
        x--; y--;

        int lc = lca(x, y);

        if (x != lc)
            swap(x, y);

        U[i] = x; V[i] = y;

        if (x == lc){
            ad[y]++;
            int PR = pra(y, x);
            ad[PR]--;
        } else {
            ad[x]++;
            ad[y]++;
            int pr1 = pra(x, y);
            int pr2 = pra(y, x);
            ad[pr1]--;
            ad[pr2]--;
        }
    }

    DFS(0);

    for (int i = 0; i < m; i++){
        int x = get(U[i]), y = get(V[i]);

        if (lca(U[i], V[i]) == U[i]) continue;

        if (x == y) BAD();

        gr[x].PB(y);
        gr[y].PB(x);
    }

    for (int i = 1; i < n; i++){
        int x = get(i);

        if (col[x] > 0) continue;

        ans += ans;
        if (ans >= md)
            ans -= md;

        rec(x, 1);
    }

    cout << ans;

    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 74292 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 14 ms 14720 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14592 KB Output is correct
2 Correct 15 ms 14720 KB Output is correct

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 56732 KB Output is correct
2 Correct 541 ms 57396 KB Output is correct
3 Correct 296 ms 40776 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 58756 KB Output is correct
2 Correct 607 ms 59000 KB Output is correct
3 Correct 369 ms 41976 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 58924 KB Output is correct
2 Correct 508 ms 57076 KB Output is correct
3 Correct 360 ms 41848 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 59880 KB Output is correct
2 Correct 623 ms 59072 KB Output is correct
3 Correct 301 ms 40688 KB Output is correct