Submission #673722

#	Time	Username	Problem	Language	Result	Execution time	Memory
673722		MilosMilutinovic	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	604 ms	103540 KiB

usmjeri

/**
 *    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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14