oj.uz

답안 #763473

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763473 2023-06-22T10:58:04 Z fanwen Usmjeri (COCI17_usmjeri) C++17
140 / 140
 357 ms 82380 KB 
/**
 *      author : pham van sam
 *      created : 22 June 2023 (Thursday)
 **/

#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)

template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }

const int MAXN = 3e5 + 5;

int N, M, depth[MAXN], anc[MAXN][20], Min[MAXN];
vector <int> adj[MAXN];

void dfs(int u, int p) {
    anc[u][0] = p;
    depth[u] = Min[u] = depth[p] + 1;
    FOR(i, 1, 19) anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (auto v : adj[u]) if(v != p) {
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);
    FORD(i, 19, 0) if(depth[anc[u][i]] >= depth[v]) {
        u = anc[u][i];
    }
    FORD(i, 19, 0) if(anc[u][i] != anc[v][i]) {
        u = anc[u][i];
        v = anc[v][i];
    }
    while(u != v) {
        u = anc[u][0];
        v = anc[v][0];
        // cout << u << " " << v << '\n';
    }
    return u;
}

vector <pair <int, int>> ke[MAXN];

void add_edges(int u, int v, int c) {
    ke[u].emplace_back(v, c);
    ke[v].emplace_back(u, c);
}

void DFS(int u, int p) {
    for (auto v : adj[u]) if(v != p) {
        DFS(v, u);
        minimize(Min[u], Min[v]);
        if(Min[v] < depth[u]) add_edges(u, v, 0);
    }
}

int used[MAXN];

bool calc(int u, int c) {
    if(used[u] != -1) return used[u] == c;
    used[u] = c;
    for (auto [v, x] : ke[u]) {
        if(!calc(v, x ^ c)) return false;
    }
    return true;
}

void process(void) {
	cin >> N >> M;
	FOR(i, 2, N) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
    dfs(1, 0);
    while(M--) {
        int u, v; cin >> u >> v;
        int x = lca(u, v);
        minimize(Min[u], depth[x]);
        minimize(Min[v], depth[x]);
        if(x != u && x != v) add_edges(u, v, 1);
    }
    DFS(1, 0);
    memset(used, -1, sizeof used);
    int res = 1, Mod = 1e9 + 7;
    FOR(i, 2, N) if(used[i] == -1) {
        if(!calc(i, 0)) return void(cout << 0);
        (res *= 2) %= Mod;
    }
    cout << res;
}

signed main() {

    #define TASK "usmjeri"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    auto start_time = steady_clock::now();
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; ++i) {
        process();
        // cout << '\n';
    }

    auto end_time = steady_clock::now();

    cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
usmjeri.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15724 KB Output is correct
2 Correct 9 ms 15852 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16340 KB Output is correct
2 Correct 10 ms 16200 KB Output is correct

Subtask #6
14.0 / 14.0

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

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 347 ms 61952 KB Output is correct
2 Correct 357 ms 63780 KB Output is correct
3 Correct 177 ms 46560 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 354 ms 65996 KB Output is correct
2 Correct 331 ms 65876 KB Output is correct
3 Correct 227 ms 50388 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 339 ms 66636 KB Output is correct
2 Correct 331 ms 62888 KB Output is correct
3 Correct 221 ms 50376 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 67056 KB Output is correct
2 Correct 340 ms 67528 KB Output is correct
3 Correct 218 ms 47152 KB Output is correct