oj.uz

Submission #328962

# Submission time Handle Problem Language Result Execution time Memory
328962 2020-11-18T15:18:13 Z marlicu Usmjeri (COCI17_usmjeri) C++14
140 / 140
 529 ms 91884 KB 
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

typedef pair <int, int> pii;

const int MOD = 1e9 + 7;
const int MAXN = 3e5 + 5;
const int LOG = 20;

int n, m;
vector <int> veze[MAXN];
vector <pii> obojano[MAXN];
int lca[LOG][MAXN];
int dubina[MAXN];
int jednak[MAXN];
int finito[MAXN];

void dfs_lca(int cvor, int pcvor, int tdubina) {
    dubina[cvor] = tdubina;
    for (auto ncvor : veze[cvor]) {
        if (ncvor == pcvor) continue;
        dfs_lca(ncvor, cvor, tdubina + 1);
        lca[0][ncvor] = cvor;
    }
}

int nadi_lca(int a, int b) {
    if (dubina[a] < dubina[b]) swap(a, b);

    for (int i = LOG - 1; i >= 0; i--) {
        if (dubina[a] - (1 << i) < dubina[b]) continue;
        a = lca[i][a];
    }

    if (a == b) return a;

    for (int i = LOG - 1; i >= 0; i--) {
        if (lca[i][a] == lca[i][b]) continue;
        a = lca[i][a]; b = lca[i][b];
    }

    return lca[0][a];
}

int spoji(int cvor, int pcvor) {
    for (auto ncvor : veze[cvor]) {
        if (ncvor == pcvor) continue;
        int nspoji = spoji(ncvor, cvor);
        jednak[cvor] = min(jednak[cvor], nspoji);
        if (nspoji < dubina[cvor]) {
            obojano[cvor].push_back({ncvor, 0});
            obojano[ncvor].push_back({cvor, 0});
        }
    }
    return jednak[cvor];
}

int dfs(int cvor, int boja) {
    if (finito[cvor] != -1) return finito[cvor] == boja;
    finito[cvor] = boja;

    for (auto ncvor : obojano[cvor]) {
        if (!dfs(ncvor.X, boja ^ ncvor.Y)) return false;
    }

    return true;
}

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

    memset(finito, -1, sizeof(finito));

    cin >> n >> m;

    int a, b;
    for (int i = 1; i < n; i++) {
        cin >> a >> b;
        veze[a].push_back(b);
        veze[b].push_back(a);
    }

    dfs_lca(1, -1, 1);
    for (int i = 1; i < LOG; i++) {
        for (int j = 1; j <= n; j++) {
            lca[i][j] = lca[i - 1][lca[i - 1][j]];
        }
    }

    for (int i = 0; i < MAXN; i++) jednak[i] = dubina[i];

    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        int zajednicki = nadi_lca(a, b);
        jednak[a] = min(jednak[a], dubina[zajednicki]);
        jednak[b] = min(jednak[b], dubina[zajednicki]);
        if (a != zajednicki && b != zajednicki) {
            obojano[a].push_back({b, 1});
            obojano[b].push_back({a, 1});
        }
    }

    spoji(1, -1);

    long long nacini = 1;
    for (int i = 2; i <= n; i++) {
        if (finito[i] != -1) continue;
        if (!dfs(i, 0)) {
            nacini = 0;
            break;
        }
        nacini *= 2;
        nacini %= MOD;
    }

    cout << nacini << '\n';

    /*
    for (int i = 1; i <= n; i++) cout << dubina[i] << " "; cout << '\n';
    for (int i = 1; i <= n; i++) cout << jednak[i] << " "; cout << '\n';
    for (int i = 1; i <= n; i++) {
        cout << i << " : ";
        for (auto nx : obojano[i]) {
            cout << nx.first << " " << nx.second << " , ";
        }
        cout << '\n';
    }
    */

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 43512 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 91884 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17004 KB Output is correct
2 Correct 12 ms 17132 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17772 KB Output is correct
2 Correct 14 ms 17516 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 62584 KB Output is correct
2 Correct 384 ms 64108 KB Output is correct
3 Correct 251 ms 47212 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 66512 KB Output is correct
2 Correct 484 ms 66540 KB Output is correct
3 Correct 311 ms 51052 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 67052 KB Output is correct
2 Correct 376 ms 63212 KB Output is correct
3 Correct 342 ms 51180 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 67692 KB Output is correct
2 Correct 416 ms 67948 KB Output is correct
3 Correct 251 ms 47980 KB Output is correct