Submission #816945

#	Time	Username	Problem	Language	Result	Execution time	Memory
816945		Theo830	Usmjeri (COCI17_usmjeri)	C++17	140 / 140	372 ms	119244 KiB

usmjeri

#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a;i < b;i++)
#define ll long long
#define ii pair<ll,ll>
#define pb push_back
#define F first
#define S second
const ll mod = 1e9+7;
vector<vector<ll> >adj;
vector<vector<ii> >graph;
ll depth[300005] = {0};
ll sum[300005] = {0};
ll an[300005][20];
ll v[300005];
void dfs(ll idx,ll p){
    an[idx][0] = p;
    f(j,1,20){
        an[idx][j] = an[an[idx][j-1]][j - 1];
    }
    for(auto x:adj[idx]){
        if(x != p){
            depth[x] = depth[idx] + 1;
            dfs(x,idx);
        }
    }
}
ll kth(ll a,ll k){
    ll pos = 0;
    while(k){
        if(k % 2){
            a = an[a][pos];
        }
        pos++;
        k /= 2;
    }
    return a;
}
void lca(ll a,ll b){
    if(a == b){
        return;
    }
    if(depth[a] > depth[b]){
        swap(a,b);
    }
    ll A = a,B = b;
    b = kth(b,depth[b] - depth[a]);
    if(a == b){
        sum[B]++;
        sum[kth(B,depth[B] - depth[a] - 1)]--;
        return;
    }
    for(ll j = 19;j >= 0;j--){
        if(an[a][j] != an[b][j]){
            a = an[a][j];
            b = an[b][j];
        }
    }
    graph[a].pb(ii(b,1));
    graph[b].pb(ii(a,1));
    sum[B]++;
    sum[A]++;
    sum[a]--;
    sum[b]--;
}
void dfs2(ll idx,ll p){
    for(auto x:adj[idx]){
        if(x != p){
            dfs2(x,idx);
            sum[idx] += sum[x];
        }
    }
    for(auto x:adj[idx]){
        if(x != p){
            if(sum[x] > 0){
                graph[x].pb(ii(idx,0));
                graph[idx].pb(ii(x,0));
            }
        }
    }
}
ll ans = 1;
void solve(ll idx,ll cur){
    v[idx] = cur;
    for(auto x:graph[idx]){
        if(v[x.F] == -1){
            solve(x.F,(cur ^ x.S));
        }
        else if(v[x.F] != (cur ^ x.S)){
            ans = 0;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,m;
    cin>>n>>m;
    adj.assign(n+5,vector<ll>());
    graph.assign(n+5,vector<ii>());
    f(i,0,n-1){
        ll a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(1,0);
    f(i,0,m){
        ll a,b;
        cin>>a>>b;
        lca(a,b);
    }
    memset(v,-1,sizeof v);
    dfs2(1,0);
    f(i,2,n+1){
        if(v[i] == -1){
            solve(i,0);
            ans *= 2;
            ans %= mod;
        }
    }
    cout<<ans<<"\n";
}

• 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