oj.uz

Submission #81022

# Submission time Handle Problem Language Result Execution time Memory
81022 2018-10-23T13:53:47 Z ngot23 Usmjeri (COCI17_usmjeri) C++11
0 / 140
 534 ms 90224 KB 
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=300005;
const int mod=1000000007;
int par[N][22], n, m, h[N], d[N], dd[N];
vector <int > g[N];
vector <pair<int, int > > g2[N];

void setup() {
    cin >> n >> m;
    rep(i, 2, n) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
}

void DFS(int u) {
    for(int v:g[u]) {
        if(v==par[u][0]) continue;
        par[v][0]=u;
        rep(i, 1, 18) par[v][i]=par[par[v][i-1]][i-1];
        d[v]=d[u]+1;
        DFS(v);
    }
}

int LCA(int u, int v) {
    if(h[u]<h[v]) swap(u, v);
    int delta=h[u]-h[v];
    rep(i, 0, 18) {
        if((delta>>i)&1) u=par[u][i];
    }
    if(u==v) return u;
    for(int i=18 ; i>=0 ; --i) {
        if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
    }
    return par[u][0];
}

int build(int u) {
    for(int v:g[u]) {
        if(v==par[u][0]) continue;
        int val=build(v);
        h[u]=min(h[u], val);
        if(val<d[u]) {
            g2[u].push_back(make_pair(v, 0));
            g2[v].push_back(make_pair(u, 0));
        }
    }
    return h[u];
}

bool DFS2(int u, bool color) {
    if(dd[u]!=-1) {
        if(dd[u]!=color) return 0;
        return 1;
    } else dd[u]=color;
    for(auto P:g2[u]) {
        if(!DFS2(P.first, color^P.second)) return 0;
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    setup();
    DFS(1);
    int ans=1;
    rep(i, 1, n) h[i]=d[i];
    while(m--) {
        int u, v;
        cin >> u >> v;
        int cha=LCA(u, v);
        h[u]=min(h[u], d[cha]);
        h[v]=min(h[v], d[cha]);
        if(u!=cha&&v!=cha) {
                g2[u].push_back(make_pair(v, 1));
                g2[v].push_back(make_pair(u, 1));
        }
    }
    build(1);
    memset(dd, -1, sizeof dd);
    rep(i, 2, n) {
        if(dd[i]==-1) {
            bool ok=DFS2(i, 0);
            if(ok==false) return cout << 0, 0;
            ans=(ans*2ll)%mod;
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 235 ms 43768 KB Output isn't correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 439 ms 90224 KB Output isn't correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 90224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 90224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 90224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 90224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 512 ms 90224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 486 ms 90224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 526 ms 90224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 534 ms 90224 KB Output isn't correct
2 Halted 0 ms 0 KB -