Submission #554767

#	Time	Username	Problem	Language	Result	Execution time	Memory
554767		600Mihnea	Jail (JOI22_jail)	C++17	Compilation error	0 ms	0 KiB

jail

#include <bits/stdc++.h>

bool home = 1;

using namespace std;

const int N = 120000 + 7; // change this!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
const int K = 20;
int n;
int m;
int vis[2 * N];
int act[2 * N];
vector<int> g[N];
vector<int> relations[2 * N];
vector<int> relations_inv[2 * N];
pair<int, int> paths[N];
int first[N];
int last[N];
int top;
int depth[N];
int par[N];
int lg[2 * N];
int is_edge1[2 * N];
int is_edge2[2 * N];
pair<int, int> rmq[K][N];

void dfs(int a, int p, int dep) {
  depth[a] = dep;
  {
    vector<int> kids;
    for (auto &b : g[a]) {
      if (b == p) continue;
      kids.push_back(b);
      par[b] = a;
    }
    g[a] = kids;
  }
  rmq[0][++top] = {dep, a};
  first[a] = last[a] = top;

  for (auto &b : g[a]) {
    dfs(b, a, dep + 1);
    rmq[0][++top] = {dep, a};
    last[a] = top;
  }
}

int get_lca(int a, int b) {
  assert(1 <= a && a <= n);
  assert(1 <= b && b <= n);
  if (first[a] > last[b]) swap(a, b);
  a = first[a];
  b = last[b];
  assert(a <= b);
  int k = lg[b - a + 1];
  return min(rmq[k][a], rmq[k][b - (1 << k) + 1]).second;
}

bool is_on_path(int a, int query, int b) {
  int c = get_lca(a, b);
  if (get_lca(c, query) == c) {
    return get_lca(a, query) == query || get_lca(b, query) == query;
  }
  return 0;
}

vector<int> ord, now;

void dfs(int a) {
  vis[a] = 1;
  for (auto &b : relations[a]) if (!vis[b]) dfs(b);
  ord.push_back(a);
}

void dfs2(int a) {
  now.push_back(a);
  vis[a] = 1;
  for (auto &b : relations_inv[a]) if (!vis[b]) dfs2(b);
}

signed main() {
#ifdef ONLINE_JUDGE
  home = 0;
#endif
  home = 0;

  if (home) {
    freopen("I_am_iron_man", "r", stdin);
  }
  else {
    ios::sync_with_stdio(0); cin.tie(0);
  }


  int Tests;
  cin >> Tests;
  for (int tc = 1; tc <= Tests; tc++) {
    cin >> n;
    ord.clear();
    for (int i = 1; i <= n; i++) g[i].clear(), is_edge1[i] = is_edge2[i] = 0;
    for (int i = 1; i <= 2 * n; i++) relations[i].clear(), vis[i] = 0, relations_inv[i].clear();
    for (int i = 1; i < n; i++) {
      int a, b;
      cin >> a >> b;
      g[a].push_back(b);
      g[b].push_back(a);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
      cin >> paths[i].first >> paths[i].second;
    }
    top = 0;
    dfs(1, -1, 0);
    for (int i = 2; i <= top; i++) {
      lg[i] = 1 + lg[i / 2];
    }
    for (int k = 1; (1 << k) <= top; k++) {
      for (int i = 1; i + (1 << k) - 1 <= top; i++) {
        rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
      }
    }

    for (int i = 1; i <= m; i++) {
      int a = paths[i].first, b = paths[i].second;
      int c = get_lca(a, b);

      vector<int> path1, path2;
      while (a != c) {
        path1.push_back(a);
        a = par[a];
      }
      while (b != c) {
        path2.push_back(b);
        b = par[b];
      }
      vector<int> path;
      for (auto &v : path1) {
        path.push_back(v);
      }
      path.push_back(c);
      reverse(path2.begin(), path2.end());
      for (auto &v : path2) {
        path.push_back(v);
      }

      for (int j = 0; j < (int) path.size(); j++) {
        relations[n + i].push_back(path[j]);
      }

    for (int i = 1; i <= m; i++) {
      int x = paths[i].first, y = paths[i].second;
      relations[x].push_back(n + i);
      relations[n + i].push_back(y);
    }


    int good = 1;

    for (int i = 1; i <= n + m; i++) {
      for (auto &j : relations[i]) {
        relations_inv[j].push_back(i);
      }
    }

    for (int i = 1; i <= n + m; i++) if (!vis[i]) dfs(i);
    for (int i = 1; i <= n + m; i++) vis[i] = 0;
    reverse(ord.begin(), ord.end());
    assert((int) ord.size() == n + m)
;    for (auto &x : ord) if (!vis[x]) {
      now.clear(), dfs2(x);
      int cnt = 0;
      for (auto &v : now) {
        cnt += (v > n);
        assert(1 <= v && v <= n + m);
      }
      if (cnt >= 2) {
        good = 0;
      }
    }


    cout << ((good) ? ("Yes") : ("No")) << "\n";
  }

}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:185:1: error: expected '}' at end of input
  185 | }
      | ^
jail.cpp:81:15: note: to match this '{'
   81 | signed main() {
      |               ^
jail.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~