oj.uz

Submission #930058

# Submission time Handle Problem Language Result Execution time Memory
930058 2024-02-18T11:44:31 Z ttamx Usmjeri (COCI17_usmjeri) C++14
140 / 140
 207 ms 61264 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=3e5+5;
const int MOD=1e9+7;

int n,m;
vector<int> adj[N];
vector<pair<int,int>> adj2[N];
int pa[N],lv[N],sz[N],hv[N],hd[N],top[N],col[N];
int ans=1;

void dfs(int u,int p=0){
    sz[u]=1;
    for(auto v:adj[u])if(v!=p){
        pa[v]=u;
        lv[v]=lv[u]+1;
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[hv[u]])hv[u]=v;
    }
}
 
void hld(int u,int p=0){
    if(!hd[u])hd[u]=u;
    if(hv[u])hd[hv[u]]=hd[u],hld(hv[u],u);
    for(auto v:adj[u])if(v!=p&&v!=hv[u])hld(v,u);
}
 
int lca(int u,int v){
    while(hd[u]!=hd[v]){
        if(lv[hd[u]]<lv[hd[v]])swap(u,v);
        u=pa[hd[u]];
    }
    return lv[u]<lv[v]?u:v;
}

void link(int u,int p=0){
    for(auto v:adj[u])if(v!=p){
        link(v,u);
        top[u]=min(top[u],top[v]);
        if(top[v]<lv[u]){
            adj2[u].emplace_back(v,0);
            adj2[v].emplace_back(u,0);
        }
    }
}

bool is_bipatite(int u,int p=0){
    for(auto [v,w]:adj2[u])if(v!=p){
        if(!col[v]){
            col[v]=col[u]^w;
            if(!is_bipatite(v,u))return false;
        }else if((col[u]^col[v])!=w)return false;
    }
    return true;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1);
    hld(1);
    for(int i=1;i<=n;i++)top[i]=lv[i];
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        int a=lca(u,v);
        top[u]=min(top[u],lv[a]);
        top[v]=min(top[v],lv[a]);
        if(u!=a&&v!=a){
            adj2[u].emplace_back(v,1);
            adj2[v].emplace_back(u,1);
        }
    }
    link(1);
    for(int i=2;i<=n;i++)if(!col[i]){
        col[i]=2;
        if(!is_bipatite(i))cout << 0,exit(0);
        ans*=2;
        if(ans>=MOD)ans-=MOD;
    }
    cout << ans;
}

Compilation message

usmjeri.cpp: In function 'bool is_bipatite(int, int)':
usmjeri.cpp:51:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for(auto [v,w]:adj2[u])if(v!=p){
      |              ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 34900 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 61264 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20572 KB Output is correct
2 Correct 5 ms 20572 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20568 KB Output is correct
2 Correct 6 ms 20572 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20824 KB Output is correct
2 Correct 6 ms 20828 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20828 KB Output is correct
2 Correct 6 ms 20824 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 35744 KB Output is correct
2 Correct 207 ms 43600 KB Output is correct
3 Correct 109 ms 35340 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 39764 KB Output is correct
2 Correct 199 ms 45684 KB Output is correct
3 Correct 137 ms 39032 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 40276 KB Output is correct
2 Correct 205 ms 42492 KB Output is correct
3 Correct 132 ms 38992 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 40636 KB Output is correct
2 Correct 195 ms 47148 KB Output is correct
3 Correct 132 ms 35620 KB Output is correct