oj.uz

답안 #62580

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
62580 2018-07-29T08:03:42 Z win11905 Usmjeri (COCI17_usmjeri) C++11
140 / 140
 827 ms 146044 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define x first
#define y second

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

int n, m, dep[N], col[N], high[N], par[N][19];
vector<int> g[N];
vector<pii> E[N];

void init_lca(int u, int p) {
    dep[u] = dep[p]+1, par[u][0] = p;
    for(int i = 1; i < 19; ++i) par[u][i] = par[par[u][i-1]][i-1];
    for(int v : g[u]) if(v != p) init_lca(v, u);
}

int get_lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 18; ~i; --i) if(dep[par[a][i]] >= dep[b]) a = par[a][i];
    if(a == b) return a;
    for(int i = 18; ~i; --i) if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
    return par[a][0];
}

void build(int u, int p) {
    for(int v : g[u]) if(v != p) {
        build(v, u), high[u] = min(high[u], high[v]); 
        if(high[v] < dep[u]) 
            E[u].emplace_back(v, 0), E[v].emplace_back(u, 0);
    }
}

bool dfs(int u, int c) {
    if(col[u] != -1) return col[u] == c;
    col[u] = c;
    for(pii v : E[u]) if(!dfs(v.x, c ^ v.y)) return false;
    return true;
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1, a, b; i < n; ++i) {
        scanf("%d %d", &a, &b);
        g[a].emplace_back(b), g[b].emplace_back(a);
    }
    init_lca(1, 0);
    for(int i = 1; i <= n; ++i) high[i] = dep[i];
    for(int i = 0, u, v; i < m; ++i) {
        scanf("%d %d", &u, &v);
        int lca = get_lca(u, v);
        high[u] = min(high[u], dep[lca]);
        high[v] = min(high[v], dep[lca]);
        if(u != lca && v != lca) 
            E[u].emplace_back(v, 1), E[v].emplace_back(u, 1);            
    }
    build(1, 0);
    memset(col, -1, sizeof col);
    int ans = 1;
    for(int i = 2; i <= n; ++i) if(col[i] == -1) {
        if(!dfs(i, 0)) return !printf("0");
        ans = ans * 2 % M; 
    }
    return !printf("%d\n", ans);
}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
usmjeri.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
usmjeri.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 797 ms 84732 KB Output is correct
2 Correct 736 ms 84732 KB Output is correct
3 Correct 407 ms 84732 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 819 ms 95628 KB Output is correct
2 Correct 702 ms 103172 KB Output is correct
3 Correct 610 ms 103172 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 787 ms 116848 KB Output is correct
2 Correct 757 ms 120588 KB Output is correct
3 Correct 514 ms 120588 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 827 ms 137752 KB Output is correct
2 Correct 709 ms 146044 KB Output is correct
3 Correct 452 ms 146044 KB Output is correct