Submission #81023

#	Time	Username	Problem	Language	Result	Execution time	Memory
81023		ngot23	Usmjeri (COCI17_usmjeri)	C++11	140 / 140	566 ms	82400 KiB

usmjeri

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14