oj.uz

Submission #878351

# Submission time Handle Problem Language Result Execution time Memory
878351 2023-11-24T08:32:49 Z noiaint Usmjeri (COCI17_usmjeri) C++17
140 / 140
 337 ms 134996 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, m;
vector<int> adj[N];
vector<pair<int, int> > g[N];
int h[N], par[N][25];
int d[N];
int color[N];

void dfs(int u, int p) {
    par[u][0] = p;
    for (int i = 1; i < 20; ++i) par[u][i] = par[par[u][i - 1]][i - 1];
    for (int v : adj[u]) if (v != p) {
        h[v] = h[u] + 1;
        dfs(v, u);
    }
}
int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    for (int i = 19; i >= 0; --i) if (h[par[u][i]] >= h[v]) u = par[u][i];
    if (u == v) return u;
    for (int i = 19; i >= 0; --i) if (par[u][i] != par[v][i]) {
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}

void paint(int u, int p) {
    for (int v : adj[u]) if (v != p) {
        paint(v, u);
        mini(d[u], d[v]);
        if (d[v] < h[u]) {
            g[u].emplace_back(v, 0);
            g[v].emplace_back(u, 0);
        }
    }
}

bool dfs2(int u, int c) {
    if (color[u] != -1) return color[u] == c;
    color[u] = c;
    for (auto [v, cv] : g[u]) {
        if (!dfs2(v, cv ^ c)) return false;
    }
    return true;
}   

void process() {
    memset(color, -1, sizeof color);
    memset(d, 0x3f, sizeof d);
    
    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    h[0] = -1;
    dfs(1, 0);
    
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        int w = lca(u, v);
        mini(d[u], h[w]);
        mini(d[v], h[w]);
        if (u != w && v != w) {
            g[u].emplace_back(v, 1);
            g[v].emplace_back(u, 1);
        }
    }

    paint(1, 0);

    int ans = 1;
    for (int i = 2; i <= n; ++i) if (color[i] == -1) {
        if (!dfs2(i, 0)) {
            cout << 0;
            return;
        }
        ans = 1LL * ans * 2 % mod;
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    #endif

    int tc = 1;
    // cin >> tc;
    
    while (tc--) {
        process();
    }

    return 0;
}

/*

*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 85588 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 134996 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 58460 KB Output is correct
2 Correct 13 ms 58460 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 58456 KB Output is correct
2 Correct 13 ms 58640 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 58776 KB Output is correct
2 Correct 14 ms 58712 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 58760 KB Output is correct
2 Correct 14 ms 58716 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 109764 KB Output is correct
2 Correct 331 ms 112020 KB Output is correct
3 Correct 173 ms 92676 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 113916 KB Output is correct
2 Correct 317 ms 114208 KB Output is correct
3 Correct 213 ms 96596 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 114812 KB Output is correct
2 Correct 305 ms 110920 KB Output is correct
3 Correct 219 ms 96688 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 115024 KB Output is correct
2 Correct 322 ms 115536 KB Output is correct
3 Correct 195 ms 93264 KB Output is correct