Submission #554544

#	Time	Username	Problem	Language	Result	Execution time	Memory
554544		600Mihnea	Jail (JOI22_jail)	C++17	49 / 100	5060 ms	46324 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 bad;
int vis[N];
int act[N];
vector<int> g[N];
vector<int> relations[N];
pair<int, int> paths[N];
int first[N];
int last[N];
int top;
int depth[N];
int lg[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);
    }
    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;
}

void check_for_cycle(int a) {
  vis[a] = act[a] = 1;
  for (auto &b : relations[a]) {
    if (act[b]) {
      bad = 1;
    }
    if (!vis[b]) {
      check_for_cycle(b);
    }
  }
  act[a] = 0;
}

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++) {
    bad = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) g[i].clear(), relations[i].clear(), vis[i] = 0;
    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 <= n; i++) {
      assert(get_lca(i, i) == i);
      assert(get_lca(1, i) == 1);
      for (int j = 1; j <= n; j++) {
        assert(get_lca(i, j) == get_lca(j, i));
        if (1 < i && i < j) {
          cout << i << " " << j << " -> " << get_lca(i, j) << "\n";
        }
      }
    }**/

    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= m; j++) {
        if (i == j) {
          continue;
        }
        int a = paths[i].first, b = paths[i].second;
        int x = paths[j].first, y = paths[j].second;

        if (is_on_path(a, x, b)) {
          relations[i].push_back(j);
        }

        if (is_on_path(a, y, b)) {
          relations[j].push_back(i);
        }
      }
    }

    for (int i = 1; i <= n; i++) {
      if (!vis[i]) {
        check_for_cycle(i);
      }
    }

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

}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23