Submission #554958

#	Time	Username	Problem	Language	Result	Execution time	Memory
554958		600Mihnea	Jail (JOI22_jail)	C++17	49 / 100	2848 ms	1048576 KiB

jail

#include <bits/stdc++.h>

bool home = 1;

using namespace std;

///const int N = 1200 + 7; // change this!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
const int N = 120000 + 7; // change this!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
const int K = 20;
const int C = 3 + 8;
int n;
int m;
int vis[C * N];
int act[C * N];
vector<int> g[N];
vector<int> relations[C * N];
vector<int> relations_inv[C * N];
pair<int, int> paths[N];
int first[N];
int last[N];
int top;
int depth[N];
int par[N];
int sub[N];
int big[N];
int col[N];
int id[N];
int fs[N];
int ls[N];
int cur_col;
int cur_id;
int lg[2 * N];
pair<int, int> rmq[K][N];
int id_of_root[N];
int lft[4 * N];
int rgh[4 * N];

void dfs(int a, int p, int dep) {
  sub[a] = 1;
  depth[a] = dep;
  big[a] = 0;
  {
    vector<int> kids;
    for (auto &b : g[a]) {
      if (b == p) continue;
      sub[a] += sub[b];
      if (sub[b] > sub[big[a]]) {
        big[a] = b;
      }
      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);
}

void addEdge(int v1, int v2) {
  relations[v1].push_back(v2);
}

void dfsHLD(int a) {
  for (auto &b : g[a]) {
    if (b == big[a]) {
      col[b] = col[a];
      id[b] = ++cur_id;
      dfsHLD(b);
    }
  }
  for (auto &b : g[a]) {
    if (b != big[a]) {
      col[b] = ++cur_col;
      id[b] = ++cur_id;
      dfsHLD(b);
    }
  }
}

void build(int vertex, int tl, int tr) {
  if (tl == tr) {
    return;
  }
  int tm = (tl + tr) / 2;
  lft[vertex] = ++cur_id;
  build(lft[vertex], tl, tm);
  rgh[vertex] = ++cur_id;
  build(rgh[vertex], tm + 1, tr);
}

vector<int> verts;

void add(int vertex, int tl, int tr, int l, int r) {
  if (r < tl || tr < l) return;
  if (l <= tl && tr <= r) {
    verts.push_back(vertex);
    return;
  }
  int tm = (tl + tr) / 2;
  add(lft[vertex], tl, tm, l, r);
  add(rgh[vertex], tm + 1, tr, l, r);
}

void place_verts(int c, int l, int r) {
  verts.clear();
  if (l > r) return;
  assert(fs[c] <= l && l <= r && r <= ls[c]);
  add(id_of_root[c], fs[c], ls[c], l, r);
}

void buildHLD() {
  cur_col = 0;
  cur_id = 0;
  col[1] = ++cur_col;
  id[1] = ++cur_id;
  dfsHLD(1);
  for (int i = 1; i <= n; i++) {
    fs[col[i]] = id[i];
    ls[col[i]] = id[i];
  }
  for (int i = 1; i <= n; i++) {
    fs[col[i]] = min(fs[col[i]], id[i]);
    ls[col[i]] = max(ls[col[i]], id[i]);
  }
  int sum = 0;
  for (int i = 1; i <= cur_col; i++) {
    sum += ls[i] - fs[i] + 1;
  }
  assert(sum == n);
  cur_id = 0;
  for (int i = 1; i <= cur_col; i++) {
    id_of_root[i] = ++cur_id;
    build(id_of_root[i], fs[col[i]], ls[col[i]]);
  }
}

void add_to(int id, int a, int c) {
  while (a != c) {
    addEdge(id, a);
    a = par[a];
  }
  addEdge(id, a);
}

void add_from(int id, int a, int c) {
  while (a != c) {
    addEdge(n + a, id);
    a = par[a];
  }
  addEdge(n + a, id);
}

void add_to_smart(int id, int a, int c) {

}

void add_to_dumb(int id, int a, int c) {

}

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();
    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))]);
      }
    }

    buildHLD();

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


      add_to(2 * n + i, a, c);
      add_to(2 * n + i, b, c);

      add_from(2 * n + i, a, c);
      add_from(2 * n + i, b, c);

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

   /// assert(cur_id <= 4 * n);

    int dim = 2 * n + m + 2 * cur_id;

    int good = 1;

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

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


    for (int i = 1; i <= dim; i++) relations[i].clear(), vis[i] = 0, relations_inv[i].clear();

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

}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:207:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |     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