oj.uz

Submission #81023

# Submission time Handle Problem Language Result Execution time Memory
81023 2018-10-23T14:04:00 Z ngot23 Usmjeri (COCI17_usmjeri) C++11
140 / 140
 566 ms 82400 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(d[u]<d[v]) swap(u, v);
    int delta=d[u]-d[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) return (dd[u]==color);
    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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 38520 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 82400 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 82400 KB Output is correct
2 Correct 502 ms 82400 KB Output is correct
3 Correct 276 ms 82400 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 82400 KB Output is correct
2 Correct 508 ms 82400 KB Output is correct
3 Correct 367 ms 82400 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 82400 KB Output is correct
2 Correct 503 ms 82400 KB Output is correct
3 Correct 365 ms 82400 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 82400 KB Output is correct
2 Correct 530 ms 82400 KB Output is correct
3 Correct 343 ms 82400 KB Output is correct