Submission #867054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
867054	2023-10-27T15:36:13 Z	nima_aryan	Jail (JOI22_jail)	C++14	Compilation error	0 ms	0 KB

jail

/**
 *    author:  NimaAryan
 *    created: 2023-10-12 11:20:40
**/
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

void solve() {
  int N;
  cin >> N;
  vector<vector<int>> t(N);
  for (int i = 0; i < N - 1; ++i) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    t[A].push_back(B);
    t[B].push_back(A);
  }
  vector up(20, vector<int>(N, -1));
  vector<int> par(N);
  vector<int> dep(N);
  auto reroot = [&](auto self, int v, int p) -> void {
    up[0][v] = par[v] = p;
    for (int k = 1; k < 20; ++k) {
      int mid = up[k - 1][v];
      if (mid != -1) {
        up[k][v] = up[k - 1][mid];
      }
    }
    for (int u : t[v]) {
      if (u != p) {
        dep[u] = dep[v] + 1;
        self(self, u, v);
      }
    }
  };
  reroot(reroot, 0, -1);
  int M;
  cin >> M;
  vector<int> S(M), T(M);
  vector<int> whoS(N, -1), whoT(N, -1);
  for (int i = 0; i < M; ++i) {
    cin >> S[i] >> T[i];
    --S[i], --T[i];
    whoS[S[i]] = whoT[T[i]] = i;
  }
  auto jump = [&](int a, int x) {
    int at = a;
    for (int k = 0; k < 20; ++k) {
      if (x >> k & 1) {
        at = up[k][at];
        if (at == -1) {
          break;
        }
      }
    }
    return at;
  };
  auto LCA = [&](int a, int b) {
    if (dep[a] < dep[b]) {
      swap(a, b);
    }
    a = jump(a, dep[a] - dep[b]);
    if (a == b) {
      return a;
    }
    for (int k = 20 - 1; k >= 0; --k) {
      int na = up[k][a];
      int nb = up[k][b];
      if (na != nb) {
        a = na;
        b = nb;
      }
    }
    return par[a];
  };
  vector<vector<int>> h(M);
  for (int i = 0; i < M; ++i) {
    auto [s, t] = pair(S[i], T[i]);
    int lca = LCA(s, t);
    vector<int> path{lca};
    while (s != lca) {
      path.push_back(s);
      s = par[s];
    }
    while (t != lca) {
      path.push_back(t);
      t = par[t];
    }
    for (int x : path) {
      if (whoS[x] != -1 && whoS[x] != i) {
        h[i].push_back(whoS[x]);
      }
      if (whoT[x] != -1 && whoT[x] != i) {
        h[whoT[x]].push_back(i);
      }
    }
  }
  vector<int> vis(M);
  bool fail = false;
  auto dfs = [&](auto self, int v) -> void {
    vis[v] = 1;
    for (int u : h[v]) {
      if (!vis[u]) {
        self(self, u);
      } else if (vis[u] == 1) {
        fail = true;
      }
    }
    vis[v] = 2;
  };
  for (int i = 0; i < M; ++i) {
    if (!vis[i]) {
      dfs(dfs, i);
    }
  }
  cout << (fail ? "No" : "Yes") << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int Q;
  cin >> Q;
  while (Q--) {
    solve();
  }
  return 0;
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:28:10: error: missing template arguments before 'up'
   28 |   vector up(20, vector<int>(N, -1));
      |          ^~
jail.cpp: In lambda function:
jail.cpp:32:5: error: 'up' was not declared in this scope; did you mean 'p'?
   32 |     up[0][v] = par[v] = p;
      |     ^~
      |     p
jail.cpp: In lambda function:
jail.cpp:60:14: error: 'up' was not declared in this scope; did you mean 'jump'?
   60 |         at = up[k][at];
      |              ^~
      |              jump
jail.cpp: In lambda function:
jail.cpp:77:16: error: 'up' was not declared in this scope; did you mean 'jump'?
   77 |       int na = up[k][a];
      |                ^~
      |                jump
jail.cpp: In function 'void solve()':
jail.cpp:88:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     auto [s, t] = pair(S[i], T[i]);
      |          ^
jail.cpp:88:23: error: missing template arguments before '(' token
   88 |     auto [s, t] = pair(S[i], T[i]);
      |                       ^