제출 #1284354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284354		warrenn	Usmjeri (COCI17_usmjeri)	C++20	56 / 140	2099 ms	79192 KiB

usmjeri

#include<bits/stdc++.h>
using namespace std; 
#define int long long 
#pragma GCC optimize("O3,unroll-loops")

const int maxn=3e5;
const int mod=1e9+7;

int pang(int a,int b){
    if(b==0)return 1;
    int tmp=pang(a,b/2);
    if(b%2==0)return (tmp*tmp)%mod;
    else return (((tmp*tmp)%mod)*a)%mod;
}

int n,qu;
vector<int>adj[maxn+2];
int bin[maxn+2][20],dep[maxn+2];

void dfs(int cur,int par){
    bin[cur][0]=par;
    dep[cur]=dep[par]+1;

    for(auto x : adj[cur]){
        if(x==par)continue;
        dfs(x,cur);
    }
}

int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int slsh=dep[u]-dep[v];

    for(int q=19;q>=0;q--){
        if(slsh>=(1<<q)){
            slsh-=(1<<q);
            u=bin[u][q];
        }
    }

    if(u==v)return u;
    for(int q=19;q>=0;q--){
        if(bin[u][q]!=bin[v][q]){
            u=bin[u][q];
            v=bin[v][q];
        }
    }
    return bin[u][0];
}

int dsu[2*maxn+2];

int fin(int a){
    if(dsu[a]==a)return a;
    return dsu[a]=fin(dsu[a]);
}

void merg(int a,int b){
    a=fin(a); b=fin(b);
    if(a==b)return ;
    dsu[a]=b;
}

signed main(){
    cin>>n>>qu;
    for(int q=1;q<n;q++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int q=1;q<=2*n;q++)dsu[q]=q;
    

    dfs(1,0);
    for(int q=1;q<20;q++){
        for(int w=1;w<=n;w++){
            bin[w][q]=bin[bin[w][q-1]][q-1];
        }
    }

    for(int q=1;q<=qu;q++){
        int u,v;
        cin>>u>>v;
        int root=lca(u,v);

        
        while(dep[u]-dep[root]>=2){
            merg(u,bin[u][0]);
            merg(u+n,bin[u][0]+n);
            u=bin[u][0];
        }

        while(dep[v]-dep[root]>=2){
            merg(v,bin[v][0]);
            merg(v+n,bin[v][0]+n);
            v=bin[v][0];
        }

        if(root==u || root==v)continue;
        merg(u,v+n);
        merg(v,u+n);

    }

    
    for(int q=1;q<=n;q++){
        if(fin(q)==fin(n+q)){
            cout<<0<<endl;
            return 0;
        }
    }

    int cc=1;
    for(int q=1;q<=2*n;q++){
        if(fin(q)==q)cc++;
    }
    cc-=2;
    cout<<pang(2,cc/2)<<endl;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14