oj.uz

Submission #930057

# Submission time Handle Problem Language Result Execution time Memory
930057 2024-02-18T11:43:28 Z ttamx Usmjeri (COCI17_usmjeri) C++14
28 / 140
 209 ms 66892 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]^2;
            if(!is_bipatite(v,u))return false;
        }else if(col[u]==col[v])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]=1;
        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 57 ms 37840 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 66892 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 20568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 20572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 20824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 21340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 41808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 45652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 46336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 46928 KB Output isn't correct
2 Halted 0 ms 0 KB -