oj.uz

Submission #673722

# Submission time Handle Problem Language Result Execution time Memory
673722 2022-12-21T20:12:24 Z MilosMilutinovic Usmjeri (COCI17_usmjeri) C++14
140 / 140
 604 ms 103540 KB 
/**
 *    author:  wxhtzdy
 *    created: 21.12.2022 20:56:30
**/
#include <bits/stdc++.h>

using namespace std;

const int md = 1e9 + 7;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    g[u].emplace_back(v, i);
    g[v].emplace_back(u, i);
  }                                   
  const int L = 25;
  vector<vector<int>> pr(L, vector<int>(n));
  vector<int> dep(n);
  vector<int> idx(n);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    pr[0][v] = pv;
    dep[v] = dep[pv] + 1;
    for (auto& p : g[v]) {
      int u = p.first;
      if (u == pv) {
        continue;
      }
      dep[u] = dep[v] + 1;
      idx[u] = p.second;
      Dfs(u, v);
    }
  };
  Dfs(0, 0);
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      pr[j][i] = pr[j - 1][pr[j - 1][i]];
    }
  }
  auto LCA = [&](int x, int y) {
    if (dep[x] < dep[y]) {
      swap(x, y);
    }
    for (int i = L - 1; i >= 0; i--) {
      if (dep[pr[i][x]] >= dep[y]) {
        x = pr[i][x];
      }
    }
    if (x == y) {
      return x;
    }
    for (int i = L - 1; i >= 0; i--) {
      if (pr[i][x] != pr[i][y]) {
        x = pr[i][x];
        y = pr[i][y];
      }
    }
    return pr[0][x];
  };
  auto Lift = [&](int x, int k) {
    for (int i = L - 1; i >= 0; i--) {
      if (k >> i & 1) {
        x = pr[i][x];
      }
    }
    return x;
  };
  vector<int> mn(n, 1e9);
  vector<vector<pair<int, int>>> e(n);
  auto AddEdge = [&](int x, int y, int w) {
    e[x].emplace_back(y, w);
    e[y].emplace_back(x, w);
  };
  while (m--) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    int z = LCA(x, y);
    if (x != z) {
      mn[x] = min(mn[x], dep[z]);
    }
    if (y != z) {
      mn[y] = min(mn[y], dep[z]);
    }
    if (x != z && y != z) {
      AddEdge(idx[Lift(x, dep[x] - dep[z] - 1)], idx[Lift(y, dep[y] - dep[z] - 1)], 1);
    }
  }                       
  function<void(int, int)> Build = [&](int v, int pv) {
    for (auto& p : g[v]) {
      int u = p.first;
      if (u == pv) {
        continue;
      }
      Build(u, v);
      if (mn[u] < dep[v]) {
        AddEdge(idx[u], idx[v], 0);
      }
      mn[v] = min(mn[v], mn[u]);
    }
  };
  Build(0, 0);
  vector<int> col(n - 1, -1);
  int ans = 1;
  auto NO = [&]() {
    cout << 0 << '\n';
    exit(0);
  };  
  function<void(int)> Color = [&](int v) {
    for (auto& p : e[v]) {
      int to = p.first;
      int w = p.second;
      if (col[to] == -1) {
        col[to] = col[v] ^ w;
        Color(to);
      } else {
        if (col[to] != col[v] ^ w) {
          NO();
        }
      }
    }
  };
  for (int i = 0; i < n - 1; i++) {
    if (col[i] == -1) {
      col[i] = 0;
      ans = (ans * 2) % md;
      Color(i);
    }
  }
  cout << ans << '\n';
  return 0;
}

Compilation message

usmjeri.cpp: In lambda function:
usmjeri.cpp:124:21: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  124 |         if (col[to] != col[v] ^ w) {

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 36292 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 103540 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 716 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 2 ms 724 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1460 KB Output is correct
2 Correct 3 ms 1364 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1492 KB Output is correct
2 Correct 3 ms 1364 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 70276 KB Output is correct
2 Correct 604 ms 72156 KB Output is correct
3 Correct 235 ms 47072 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 74456 KB Output is correct
2 Correct 469 ms 74172 KB Output is correct
3 Correct 344 ms 50192 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 74628 KB Output is correct
2 Correct 517 ms 71564 KB Output is correct
3 Correct 306 ms 50040 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 75360 KB Output is correct
2 Correct 451 ms 75192 KB Output is correct
3 Correct 367 ms 47792 KB Output is correct