oj.uz

Submission #554958

# Submission time Handle Problem Language Result Execution time Memory
554958 2022-04-29T18:03:44 Z 600Mihnea Jail (JOI22_jail) C++17
49 / 100
 2848 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]);
  }
  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

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.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 65228 KB Output is correct
2 Correct 36 ms 65152 KB Output is correct
3 Correct 35 ms 65224 KB Output is correct
4 Correct 51 ms 65464 KB Output is correct
5 Correct 75 ms 65412 KB Output is correct
6 Correct 38 ms 65360 KB Output is correct
7 Correct 34 ms 65404 KB Output is correct
8 Correct 37 ms 65740 KB Output is correct
9 Correct 468 ms 120372 KB Output is correct
10 Runtime error 2848 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 38 ms 65236 KB Output is correct
2 Correct 42 ms 65236 KB Output is correct
3 Correct 39 ms 65448 KB Output is correct
4 Correct 42 ms 65580 KB Output is correct
5 Correct 53 ms 65532 KB Output is correct
6 Correct 44 ms 65484 KB Output is correct
7 Correct 43 ms 65492 KB Output is correct
8 Correct 47 ms 65500 KB Output is correct
9 Correct 40 ms 65492 KB Output is correct
10 Correct 40 ms 65448 KB Output is correct
11 Correct 43 ms 65640 KB Output is correct
12 Correct 35 ms 65288 KB Output is correct
13 Correct 42 ms 65332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65236 KB Output is correct
2 Correct 42 ms 65236 KB Output is correct
3 Correct 39 ms 65448 KB Output is correct
4 Correct 42 ms 65580 KB Output is correct
5 Correct 53 ms 65532 KB Output is correct
6 Correct 44 ms 65484 KB Output is correct
7 Correct 43 ms 65492 KB Output is correct
8 Correct 47 ms 65500 KB Output is correct
9 Correct 40 ms 65492 KB Output is correct
10 Correct 40 ms 65448 KB Output is correct
11 Correct 43 ms 65640 KB Output is correct
12 Correct 35 ms 65288 KB Output is correct
13 Correct 42 ms 65332 KB Output is correct
14 Correct 35 ms 65132 KB Output is correct
15 Correct 32 ms 65228 KB Output is correct
16 Correct 37 ms 65388 KB Output is correct
17 Correct 46 ms 65400 KB Output is correct
18 Correct 37 ms 65356 KB Output is correct
19 Correct 34 ms 65180 KB Output is correct
20 Correct 37 ms 65364 KB Output is correct
21 Correct 37 ms 65432 KB Output is correct
22 Correct 40 ms 65428 KB Output is correct
23 Correct 40 ms 65132 KB Output is correct
24 Correct 33 ms 65276 KB Output is correct
25 Correct 36 ms 65364 KB Output is correct
26 Correct 33 ms 65384 KB Output is correct
27 Correct 43 ms 65288 KB Output is correct
28 Correct 35 ms 65236 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65236 KB Output is correct
2 Correct 42 ms 65236 KB Output is correct
3 Correct 39 ms 65448 KB Output is correct
4 Correct 42 ms 65580 KB Output is correct
5 Correct 53 ms 65532 KB Output is correct
6 Correct 44 ms 65484 KB Output is correct
7 Correct 43 ms 65492 KB Output is correct
8 Correct 47 ms 65500 KB Output is correct
9 Correct 40 ms 65492 KB Output is correct
10 Correct 40 ms 65448 KB Output is correct
11 Correct 43 ms 65640 KB Output is correct
12 Correct 35 ms 65288 KB Output is correct
13 Correct 42 ms 65332 KB Output is correct
14 Correct 35 ms 65132 KB Output is correct
15 Correct 32 ms 65228 KB Output is correct
16 Correct 37 ms 65388 KB Output is correct
17 Correct 46 ms 65400 KB Output is correct
18 Correct 37 ms 65356 KB Output is correct
19 Correct 34 ms 65180 KB Output is correct
20 Correct 37 ms 65364 KB Output is correct
21 Correct 37 ms 65432 KB Output is correct
22 Correct 40 ms 65428 KB Output is correct
23 Correct 40 ms 65132 KB Output is correct
24 Correct 33 ms 65276 KB Output is correct
25 Correct 36 ms 65364 KB Output is correct
26 Correct 33 ms 65384 KB Output is correct
27 Correct 43 ms 65288 KB Output is correct
28 Correct 35 ms 65236 KB Output is correct
29 Correct 43 ms 65932 KB Output is correct
30 Correct 41 ms 65416 KB Output is correct
31 Correct 37 ms 65616 KB Output is correct
32 Correct 46 ms 65444 KB Output is correct
33 Correct 39 ms 65476 KB Output is correct
34 Correct 38 ms 65480 KB Output is correct
35 Correct 45 ms 65628 KB Output is correct
36 Correct 38 ms 65348 KB Output is correct
37 Correct 42 ms 65400 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65236 KB Output is correct
2 Correct 42 ms 65236 KB Output is correct
3 Correct 39 ms 65448 KB Output is correct
4 Correct 42 ms 65580 KB Output is correct
5 Correct 53 ms 65532 KB Output is correct
6 Correct 44 ms 65484 KB Output is correct
7 Correct 43 ms 65492 KB Output is correct
8 Correct 47 ms 65500 KB Output is correct
9 Correct 40 ms 65492 KB Output is correct
10 Correct 40 ms 65448 KB Output is correct
11 Correct 43 ms 65640 KB Output is correct
12 Correct 35 ms 65288 KB Output is correct
13 Correct 42 ms 65332 KB Output is correct
14 Correct 35 ms 65132 KB Output is correct
15 Correct 32 ms 65228 KB Output is correct
16 Correct 37 ms 65388 KB Output is correct
17 Correct 46 ms 65400 KB Output is correct
18 Correct 37 ms 65356 KB Output is correct
19 Correct 34 ms 65180 KB Output is correct
20 Correct 37 ms 65364 KB Output is correct
21 Correct 37 ms 65432 KB Output is correct
22 Correct 40 ms 65428 KB Output is correct
23 Correct 40 ms 65132 KB Output is correct
24 Correct 33 ms 65276 KB Output is correct
25 Correct 36 ms 65364 KB Output is correct
26 Correct 33 ms 65384 KB Output is correct
27 Correct 43 ms 65288 KB Output is correct
28 Correct 35 ms 65236 KB Output is correct
29 Correct 43 ms 65932 KB Output is correct
30 Correct 41 ms 65416 KB Output is correct
31 Correct 37 ms 65616 KB Output is correct
32 Correct 46 ms 65444 KB Output is correct
33 Correct 39 ms 65476 KB Output is correct
34 Correct 38 ms 65480 KB Output is correct
35 Correct 45 ms 65628 KB Output is correct
36 Correct 38 ms 65348 KB Output is correct
37 Correct 42 ms 65400 KB Output is correct
38 Correct 494 ms 120352 KB Output is correct
39 Runtime error 2848 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 36 ms 65228 KB Output is correct
2 Correct 36 ms 65152 KB Output is correct
3 Correct 36 ms 65240 KB Output is correct
4 Correct 35 ms 65108 KB Output is correct
5 Correct 49 ms 65416 KB Output is correct
6 Correct 36 ms 65248 KB Output is correct
7 Correct 39 ms 65364 KB Output is correct
8 Correct 35 ms 65200 KB Output is correct
9 Correct 35 ms 65236 KB Output is correct
10 Correct 35 ms 65260 KB Output is correct
11 Correct 36 ms 65176 KB Output is correct
12 Correct 37 ms 65400 KB Output is correct
13 Correct 82 ms 65740 KB Output is correct
14 Correct 125 ms 65988 KB Output is correct
15 Correct 107 ms 65948 KB Output is correct
16 Runtime error 1022 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 37 ms 65228 KB Output is correct
2 Correct 36 ms 65152 KB Output is correct
3 Correct 35 ms 65224 KB Output is correct
4 Correct 51 ms 65464 KB Output is correct
5 Correct 75 ms 65412 KB Output is correct
6 Correct 38 ms 65360 KB Output is correct
7 Correct 34 ms 65404 KB Output is correct
8 Correct 37 ms 65740 KB Output is correct
9 Correct 468 ms 120372 KB Output is correct
10 Runtime error 2848 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -