oj.uz

답안 #930062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930062 2024-02-18T11:48:26 Z ttamx Usmjeri (COCI17_usmjeri) C++14
140 / 140
 212 ms 61328 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,int c=2){
    if(col[u])return col[u]==c;
    col[u]=c;
    for(auto [v,w]:adj2[u])if(v!=p){
        if(!is_bipatite(v,u,c^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]){
        if(!is_bipatite(i))ans=0;
        ans*=2;
        if(ans>=MOD)ans-=MOD;
    }
    cout << ans;
}

Compilation message

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

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 20572 KB Output is correct
2 Correct 5 ms 20572 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 20828 KB Output is correct
2 Correct 6 ms 20572 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 21080 KB Output is correct
2 Correct 7 ms 20572 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 35560 KB Output is correct
2 Correct 196 ms 37500 KB Output is correct
3 Correct 118 ms 32160 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 39760 KB Output is correct
2 Correct 211 ms 39644 KB Output is correct
3 Correct 147 ms 34704 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 40272 KB Output is correct
2 Correct 189 ms 36444 KB Output is correct
3 Correct 148 ms 34796 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 40788 KB Output is correct
2 Correct 195 ms 40956 KB Output is correct
3 Correct 154 ms 32984 KB Output is correct