oj.uz

Submission #816945

# Submission time Handle Problem Language Result Execution time Memory
816945 2023-08-09T07:39:50 Z Theo830 Usmjeri (COCI17_usmjeri) C++17
140 / 140
 372 ms 119244 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 43468 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 119244 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Correct 2 ms 3156 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 4 ms 4052 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 4 ms 3968 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 91644 KB Output is correct
2 Correct 349 ms 94388 KB Output is correct
3 Correct 211 ms 63280 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 99876 KB Output is correct
2 Correct 340 ms 99260 KB Output is correct
3 Correct 225 ms 68084 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 99804 KB Output is correct
2 Correct 346 ms 92968 KB Output is correct
3 Correct 222 ms 67588 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 99952 KB Output is correct
2 Correct 370 ms 99540 KB Output is correct
3 Correct 240 ms 63508 KB Output is correct