oj.uz

Submission #554952

# Submission time Handle Problem Language Result Execution time Memory
554952 2022-04-29T17:59:59 Z 600Mihnea Jail (JOI22_jail) C++17
49 / 100
 2628 ms 1048576 KB 
#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]);
  }
  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);
    }

    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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65236 KB Output is correct
2 Correct 32 ms 65200 KB Output is correct
3 Correct 32 ms 65164 KB Output is correct
4 Correct 53 ms 65424 KB Output is correct
5 Correct 75 ms 65464 KB Output is correct
6 Correct 32 ms 65356 KB Output is correct
7 Correct 33 ms 65388 KB Output is correct
8 Correct 37 ms 65732 KB Output is correct
9 Correct 443 ms 120032 KB Output is correct
10 Runtime error 2628 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65228 KB Output is correct
2 Correct 32 ms 65212 KB Output is correct
3 Correct 34 ms 65388 KB Output is correct
4 Correct 40 ms 65484 KB Output is correct
5 Correct 37 ms 65532 KB Output is correct
6 Correct 36 ms 65512 KB Output is correct
7 Correct 37 ms 65492 KB Output is correct
8 Correct 35 ms 65492 KB Output is correct
9 Correct 38 ms 65492 KB Output is correct
10 Correct 41 ms 65480 KB Output is correct
11 Correct 37 ms 65548 KB Output is correct
12 Correct 33 ms 65468 KB Output is correct
13 Correct 36 ms 65276 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65228 KB Output is correct
2 Correct 32 ms 65212 KB Output is correct
3 Correct 34 ms 65388 KB Output is correct
4 Correct 40 ms 65484 KB Output is correct
5 Correct 37 ms 65532 KB Output is correct
6 Correct 36 ms 65512 KB Output is correct
7 Correct 37 ms 65492 KB Output is correct
8 Correct 35 ms 65492 KB Output is correct
9 Correct 38 ms 65492 KB Output is correct
10 Correct 41 ms 65480 KB Output is correct
11 Correct 37 ms 65548 KB Output is correct
12 Correct 33 ms 65468 KB Output is correct
13 Correct 36 ms 65276 KB Output is correct
14 Correct 32 ms 65196 KB Output is correct
15 Correct 37 ms 65148 KB Output is correct
16 Correct 34 ms 65484 KB Output is correct
17 Correct 39 ms 65316 KB Output is correct
18 Correct 36 ms 65364 KB Output is correct
19 Correct 35 ms 65204 KB Output is correct
20 Correct 36 ms 65452 KB Output is correct
21 Correct 41 ms 65376 KB Output is correct
22 Correct 37 ms 65356 KB Output is correct
23 Correct 34 ms 65228 KB Output is correct
24 Correct 33 ms 65316 KB Output is correct
25 Correct 34 ms 65288 KB Output is correct
26 Correct 33 ms 65324 KB Output is correct
27 Correct 34 ms 65364 KB Output is correct
28 Correct 32 ms 65236 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65228 KB Output is correct
2 Correct 32 ms 65212 KB Output is correct
3 Correct 34 ms 65388 KB Output is correct
4 Correct 40 ms 65484 KB Output is correct
5 Correct 37 ms 65532 KB Output is correct
6 Correct 36 ms 65512 KB Output is correct
7 Correct 37 ms 65492 KB Output is correct
8 Correct 35 ms 65492 KB Output is correct
9 Correct 38 ms 65492 KB Output is correct
10 Correct 41 ms 65480 KB Output is correct
11 Correct 37 ms 65548 KB Output is correct
12 Correct 33 ms 65468 KB Output is correct
13 Correct 36 ms 65276 KB Output is correct
14 Correct 32 ms 65196 KB Output is correct
15 Correct 37 ms 65148 KB Output is correct
16 Correct 34 ms 65484 KB Output is correct
17 Correct 39 ms 65316 KB Output is correct
18 Correct 36 ms 65364 KB Output is correct
19 Correct 35 ms 65204 KB Output is correct
20 Correct 36 ms 65452 KB Output is correct
21 Correct 41 ms 65376 KB Output is correct
22 Correct 37 ms 65356 KB Output is correct
23 Correct 34 ms 65228 KB Output is correct
24 Correct 33 ms 65316 KB Output is correct
25 Correct 34 ms 65288 KB Output is correct
26 Correct 33 ms 65324 KB Output is correct
27 Correct 34 ms 65364 KB Output is correct
28 Correct 32 ms 65236 KB Output is correct
29 Correct 38 ms 65784 KB Output is correct
30 Correct 35 ms 65364 KB Output is correct
31 Correct 38 ms 65572 KB Output is correct
32 Correct 40 ms 65424 KB Output is correct
33 Correct 36 ms 65416 KB Output is correct
34 Correct 37 ms 65448 KB Output is correct
35 Correct 38 ms 65652 KB Output is correct
36 Correct 39 ms 65396 KB Output is correct
37 Correct 35 ms 65356 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65228 KB Output is correct
2 Correct 32 ms 65212 KB Output is correct
3 Correct 34 ms 65388 KB Output is correct
4 Correct 40 ms 65484 KB Output is correct
5 Correct 37 ms 65532 KB Output is correct
6 Correct 36 ms 65512 KB Output is correct
7 Correct 37 ms 65492 KB Output is correct
8 Correct 35 ms 65492 KB Output is correct
9 Correct 38 ms 65492 KB Output is correct
10 Correct 41 ms 65480 KB Output is correct
11 Correct 37 ms 65548 KB Output is correct
12 Correct 33 ms 65468 KB Output is correct
13 Correct 36 ms 65276 KB Output is correct
14 Correct 32 ms 65196 KB Output is correct
15 Correct 37 ms 65148 KB Output is correct
16 Correct 34 ms 65484 KB Output is correct
17 Correct 39 ms 65316 KB Output is correct
18 Correct 36 ms 65364 KB Output is correct
19 Correct 35 ms 65204 KB Output is correct
20 Correct 36 ms 65452 KB Output is correct
21 Correct 41 ms 65376 KB Output is correct
22 Correct 37 ms 65356 KB Output is correct
23 Correct 34 ms 65228 KB Output is correct
24 Correct 33 ms 65316 KB Output is correct
25 Correct 34 ms 65288 KB Output is correct
26 Correct 33 ms 65324 KB Output is correct
27 Correct 34 ms 65364 KB Output is correct
28 Correct 32 ms 65236 KB Output is correct
29 Correct 38 ms 65784 KB Output is correct
30 Correct 35 ms 65364 KB Output is correct
31 Correct 38 ms 65572 KB Output is correct
32 Correct 40 ms 65424 KB Output is correct
33 Correct 36 ms 65416 KB Output is correct
34 Correct 37 ms 65448 KB Output is correct
35 Correct 38 ms 65652 KB Output is correct
36 Correct 39 ms 65396 KB Output is correct
37 Correct 35 ms 65356 KB Output is correct
38 Correct 434 ms 119944 KB Output is correct
39 Runtime error 2618 ms 1048576 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65228 KB Output is correct
2 Correct 33 ms 65236 KB Output is correct
3 Correct 34 ms 65188 KB Output is correct
4 Correct 33 ms 65108 KB Output is correct
5 Correct 43 ms 65404 KB Output is correct
6 Correct 34 ms 65364 KB Output is correct
7 Correct 32 ms 65356 KB Output is correct
8 Correct 32 ms 65160 KB Output is correct
9 Correct 32 ms 65236 KB Output is correct
10 Correct 33 ms 65260 KB Output is correct
11 Correct 34 ms 65228 KB Output is correct
12 Correct 35 ms 65392 KB Output is correct
13 Correct 76 ms 65560 KB Output is correct
14 Correct 103 ms 65488 KB Output is correct
15 Correct 91 ms 65500 KB Output is correct
16 Runtime error 941 ms 1048576 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65236 KB Output is correct
2 Correct 32 ms 65200 KB Output is correct
3 Correct 32 ms 65164 KB Output is correct
4 Correct 53 ms 65424 KB Output is correct
5 Correct 75 ms 65464 KB Output is correct
6 Correct 32 ms 65356 KB Output is correct
7 Correct 33 ms 65388 KB Output is correct
8 Correct 37 ms 65732 KB Output is correct
9 Correct 443 ms 120032 KB Output is correct
10 Runtime error 2628 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -