| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 110070 | maruii | Usmjeri (COCI17_usmjeri) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
vector<int> edge0[300002];
vector<pii> edge[300002];
int prt[19][300002], dth[300002], par[300002];
int fnd(int x){return x==par[x]?x:par[x]=fnd(par[x]);}
void uni(int x, int y){
x = fnd(x), y = fnd(y);
if(x==y) return;
if(dth[x]<dth[y]) swap(x, y);
par[x] = y;
}
void dfs0(int x, int p){
prt[0][x] = p;
dth[x] = dth[p] + 1;
for(auto i: edge0[x]){
if(i==p) continue;
dfs0(i, x);
}
}
int lca(int x, int y){
if(dth[x]<dth[y]) swap(x, y);
for(int i=18; i>=0; --i) if(dth[prt[i][x]]>=dth[y]) x = prt[i][x];
if(x==y) return x;
for(int i=18; i>=0; --i) if(x!=y) x = prt[i][x], y = prt[i][y];
return prt[0][x];
}
const int mod = 1e9+7;
bool used[300001];
int dir[300001];
bool dfs(int x, int p, int c){
if(dir[x] != -1) return dir[x] == c;
dir[x] = c;
for(auto i: edge[x]){
if(p==i.ss) continue;
if(!dfs(i.ss, x, c ^ i.ff)) return 0;
}
return 1;
}
int main(){
ios_base::sync_with_stdio(0), cin.tie(0);
int N, M; cin>>N>>M;
for(int i=1; i<N; ++i){
int x,y; cin>>x>>y;
edge0[x].push_back(y), edge0[y].push_back(x);
}
iota(par, par+N+1, 0);
dfs0(1, 0);
for(int i=1; i<19; ++i) for(int j=1; j<=N; ++j) prt[i][j] = prt[i-1][prt[i-1][j]];
for(int i=0; i<M; ++i){
int x,y,l; cin>>x>>y;
l = lca(x, y);
if(l!=x && l!=y) edge[x].emplace_back(1, y), edge[y].emplace_back(1, x);
for(int v=fnd(x); dth[prt[0][v]]>dth[l]; v=fnd(prt[0][v])){
edge[v].emplace_back(0, prt[0][v]), edge[prt[0][v]].emplace_back(0, v);
uni(v, prt[0][v]);
}
for(int v=fnd(y); dth[prt[0][v]]>dth[l]; v=fnd(prt[0][v])){`0 10
edge[v].emplace_back(0, prt[0][v]), edge[prt[0][v]].emplace_back(0, v);
uni(v, prt[0][v]);
}
}
memset(dir, -1, sizeof(dir));
int ans = 1;
for(int i=2; i<=N; ++i) if(dir[i]==-1){
if(dfs(i, 0, 1)) ans = (ans<<1)%mod;
else return !printf("0");
}
cout<<ans;
return 0;
}