oj.uz

답안 #677902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677902 2023-01-04T15:09:47 Z Ahmed57 Usmjeri (COCI17_usmjeri) C++14
56 / 140
 719 ms 73504 KB 
#include <bits/stdc++.h>

using namespace std;
//DSU
int mn1 = 300001;
int pr1[300001],pr2[300001];
int gs1[300001],gs2[300001];
int findleader1(int x){
    if(pr1[x]==x){
        return x;
    }
    return pr1[x] = findleader1(pr1[x]);
}
bool samegroup1(int x,int y){
    int led1 = findleader1(x);
    int led2 = findleader1(y);
    return led1==led2;
}
void mergegroup1(int x,int y){
    int led1 = findleader1(x);
    int led2 = findleader1(y);
    if(led1==led2)return;
    if(gs1[led1]>gs1[led2]){
        pr1[led2]=led1;
        gs1[led1]+=gs1[led2];
    }else{
        pr1[led1]=led2;
        gs1[led2]+=gs1[led1];
    }
}
int findleader2(int x){
    if(pr2[x]==x){
        return x;
    }
    return pr2[x] = findleader2(pr2[x]);
}
bool samegroup2(int x,int y){
    int led1 = findleader2(x);
    int led2 = findleader2(y);
    return led1==led2;
}
void mergegroup2(int x,int y){
    int led1 = findleader2(x);
    int led2 = findleader2(y);
    if(led1==led2)return;
    if(gs2[led1]>gs2[led2]){
        pr2[led2]=led1;
        gs2[led1]+=gs2[led2];
    }else{
        pr2[led1]=led2;
        gs2[led2]+=gs2[led1];
    }
}
int dep[300001];
int P[300001][20];
int ed[300001];
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int k=19;k>=0;k--)
    {
        if(dep[x]-(1<<k) >= dep[y])
            x=P[x][k];
    }
    if(x==y) return x;
    for(int k=19;k>=0;k--)
    {
        if(P[x][k] != P[y][k])
            x=P[x][k],y=P[y][k];
    }
    return P[x][0];
}
vector<pair<int,int>> adj[300001];
void dfs(int i,int pr,int e){
    P[i][0] = pr;
    ed[i] = e;
    dep[i] = dep[pr]+1;
    for(int j = 1;j<20;j++){
        P[i][j] = P[P[i][j-1]][j-1];
    }
    for(auto j:adj[i]){
        if(j.first!=pr){
            dfs(j.first,i,j.second);
        }
    }
}
vector<int> e[300001];
int vis[300001] , col[300001];
bool ss = 1;
void color(int i,int c){
    vis[i] = 1;col[i] = c;
    for(auto j:e[i]){
        if(vis[j]==0){
            color(j,!c);
        }else{
            if(col[j]==c){
                ss = 0;
            }
        }
    }
}
int main(){
    //freopen("poklonin6.txt","r",stdin);
    for(int i = 0;i<mn1;i++){
        pr1[i] = i , pr2[i] = i , gs1[i] = 1, gs2[i] = 1;
    }
    int n,m;
    cin>>n>>m;
    for(int i = 0;i<n-1;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
    }
    dfs(1,0,0);
    while(m--){
        int a,b;cin>>a>>b;
        int lc = lca(a,b);
        int cur = a , last = -1;
        if(dep[a]>dep[lc]){
            last = ed[a];
        }
        while(dep[cur]>dep[lc]){
            for(int j = 19;j>=0;j--){
                if(samegroup1(cur,P[cur][j])){
                    cur = P[cur][j];
                }
            }
            if(dep[cur]>dep[lc]){
                mergegroup1(cur,P[cur][0]);
                mergegroup2(last,ed[cur]);
            }
            cur = P[cur][0];
            if(dep[cur]>dep[lc]){
                mergegroup2(last,ed[cur]);
            }
        }
        int last2 = last;
        swap(a,b);
        cur = a , last = -1;
        if(dep[a]>dep[lc]){
            last = ed[a];
        }
        while(dep[cur]>dep[lc]){
            for(int j = 19;j>=0;j--){
                if(samegroup1(cur,P[cur][j])){
                    cur = P[cur][j];
                }
            }
            if(dep[cur]>dep[lc]){
                mergegroup1(cur,P[cur][0]);
                mergegroup2(last,ed[cur]);
            }
            cur = P[cur][0];
            if(dep[cur]>dep[lc]){
                mergegroup2(last,ed[cur]);
            }
        }
        if(last!=-1&&last2!=-1){
            e[findleader2(last)].push_back(findleader2(last2));
            e[findleader2(last2)].push_back(findleader2(last));
        }
    }
    long long ans = 1;
    for(int i = 0;i<n-1;i++){
        if(!vis[findleader2(i)]){
            color(findleader2(i),0);
            ans*=2;ans%=(1000000007);
        }
    }
    if(!ss){
        cout<<"0\n";
    }else cout<<ans;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 36116 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 541 ms 73504 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 19876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 19728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 669 ms 62640 KB Output is correct
2 Correct 661 ms 67080 KB Output is correct
3 Correct 307 ms 49948 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 691 ms 64456 KB Output is correct
2 Correct 642 ms 68508 KB Output is correct
3 Incorrect 444 ms 51936 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 719 ms 64584 KB Output is correct
2 Correct 648 ms 66836 KB Output is correct
3 Correct 410 ms 52028 KB Output is correct

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 611 ms 65720 KB Output is correct
2 Incorrect 640 ms 68888 KB Output isn't correct
3 Halted 0 ms 0 KB -