oj.uz

Submission #554959

# Submission time Handle Problem Language Result Execution time Memory
554959 2022-04-29T18:05:22 Z 600Mihnea Jail (JOI22_jail) C++17
49 / 100
 2694 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 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(1, 1, n, 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;
  cur_id++;
  build(1, 1, n);
}

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:204:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65228 KB Output is correct
2 Correct 30 ms 65196 KB Output is correct
3 Correct 30 ms 65176 KB Output is correct
4 Correct 54 ms 65456 KB Output is correct
5 Correct 82 ms 65288 KB Output is correct
6 Correct 34 ms 65396 KB Output is correct
7 Correct 34 ms 65404 KB Output is correct
8 Correct 39 ms 65800 KB Output is correct
9 Correct 476 ms 120640 KB Output is correct
10 Runtime error 2694 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 39 ms 65196 KB Output is correct
2 Correct 36 ms 65228 KB Output is correct
3 Correct 43 ms 65424 KB Output is correct
4 Correct 38 ms 65268 KB Output is correct
5 Correct 35 ms 65280 KB Output is correct
6 Correct 34 ms 65408 KB Output is correct
7 Correct 37 ms 65312 KB Output is correct
8 Correct 35 ms 65380 KB Output is correct
9 Correct 39 ms 65480 KB Output is correct
10 Correct 43 ms 65356 KB Output is correct
11 Correct 37 ms 65292 KB Output is correct
12 Correct 34 ms 65284 KB Output is correct
13 Correct 34 ms 65356 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 65196 KB Output is correct
2 Correct 36 ms 65228 KB Output is correct
3 Correct 43 ms 65424 KB Output is correct
4 Correct 38 ms 65268 KB Output is correct
5 Correct 35 ms 65280 KB Output is correct
6 Correct 34 ms 65408 KB Output is correct
7 Correct 37 ms 65312 KB Output is correct
8 Correct 35 ms 65380 KB Output is correct
9 Correct 39 ms 65480 KB Output is correct
10 Correct 43 ms 65356 KB Output is correct
11 Correct 37 ms 65292 KB Output is correct
12 Correct 34 ms 65284 KB Output is correct
13 Correct 34 ms 65356 KB Output is correct
14 Correct 35 ms 65232 KB Output is correct
15 Correct 32 ms 65228 KB Output is correct
16 Correct 33 ms 65416 KB Output is correct
17 Correct 37 ms 65308 KB Output is correct
18 Correct 38 ms 65320 KB Output is correct
19 Correct 37 ms 65260 KB Output is correct
20 Correct 34 ms 65356 KB Output is correct
21 Correct 37 ms 65356 KB Output is correct
22 Correct 35 ms 65404 KB Output is correct
23 Correct 34 ms 65164 KB Output is correct
24 Correct 33 ms 65224 KB Output is correct
25 Correct 43 ms 65368 KB Output is correct
26 Correct 41 ms 65324 KB Output is correct
27 Correct 37 ms 65312 KB Output is correct
28 Correct 32 ms 65248 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 65196 KB Output is correct
2 Correct 36 ms 65228 KB Output is correct
3 Correct 43 ms 65424 KB Output is correct
4 Correct 38 ms 65268 KB Output is correct
5 Correct 35 ms 65280 KB Output is correct
6 Correct 34 ms 65408 KB Output is correct
7 Correct 37 ms 65312 KB Output is correct
8 Correct 35 ms 65380 KB Output is correct
9 Correct 39 ms 65480 KB Output is correct
10 Correct 43 ms 65356 KB Output is correct
11 Correct 37 ms 65292 KB Output is correct
12 Correct 34 ms 65284 KB Output is correct
13 Correct 34 ms 65356 KB Output is correct
14 Correct 35 ms 65232 KB Output is correct
15 Correct 32 ms 65228 KB Output is correct
16 Correct 33 ms 65416 KB Output is correct
17 Correct 37 ms 65308 KB Output is correct
18 Correct 38 ms 65320 KB Output is correct
19 Correct 37 ms 65260 KB Output is correct
20 Correct 34 ms 65356 KB Output is correct
21 Correct 37 ms 65356 KB Output is correct
22 Correct 35 ms 65404 KB Output is correct
23 Correct 34 ms 65164 KB Output is correct
24 Correct 33 ms 65224 KB Output is correct
25 Correct 43 ms 65368 KB Output is correct
26 Correct 41 ms 65324 KB Output is correct
27 Correct 37 ms 65312 KB Output is correct
28 Correct 32 ms 65248 KB Output is correct
29 Correct 39 ms 65852 KB Output is correct
30 Correct 35 ms 65412 KB Output is correct
31 Correct 36 ms 65612 KB Output is correct
32 Correct 39 ms 65484 KB Output is correct
33 Correct 38 ms 65400 KB Output is correct
34 Correct 36 ms 65356 KB Output is correct
35 Correct 37 ms 65496 KB Output is correct
36 Correct 36 ms 65336 KB Output is correct
37 Correct 34 ms 65420 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 65196 KB Output is correct
2 Correct 36 ms 65228 KB Output is correct
3 Correct 43 ms 65424 KB Output is correct
4 Correct 38 ms 65268 KB Output is correct
5 Correct 35 ms 65280 KB Output is correct
6 Correct 34 ms 65408 KB Output is correct
7 Correct 37 ms 65312 KB Output is correct
8 Correct 35 ms 65380 KB Output is correct
9 Correct 39 ms 65480 KB Output is correct
10 Correct 43 ms 65356 KB Output is correct
11 Correct 37 ms 65292 KB Output is correct
12 Correct 34 ms 65284 KB Output is correct
13 Correct 34 ms 65356 KB Output is correct
14 Correct 35 ms 65232 KB Output is correct
15 Correct 32 ms 65228 KB Output is correct
16 Correct 33 ms 65416 KB Output is correct
17 Correct 37 ms 65308 KB Output is correct
18 Correct 38 ms 65320 KB Output is correct
19 Correct 37 ms 65260 KB Output is correct
20 Correct 34 ms 65356 KB Output is correct
21 Correct 37 ms 65356 KB Output is correct
22 Correct 35 ms 65404 KB Output is correct
23 Correct 34 ms 65164 KB Output is correct
24 Correct 33 ms 65224 KB Output is correct
25 Correct 43 ms 65368 KB Output is correct
26 Correct 41 ms 65324 KB Output is correct
27 Correct 37 ms 65312 KB Output is correct
28 Correct 32 ms 65248 KB Output is correct
29 Correct 39 ms 65852 KB Output is correct
30 Correct 35 ms 65412 KB Output is correct
31 Correct 36 ms 65612 KB Output is correct
32 Correct 39 ms 65484 KB Output is correct
33 Correct 38 ms 65400 KB Output is correct
34 Correct 36 ms 65356 KB Output is correct
35 Correct 37 ms 65496 KB Output is correct
36 Correct 36 ms 65336 KB Output is correct
37 Correct 34 ms 65420 KB Output is correct
38 Correct 463 ms 120572 KB Output is correct
39 Runtime error 2674 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 34 ms 65232 KB Output is correct
2 Correct 35 ms 65180 KB Output is correct
3 Correct 36 ms 65160 KB Output is correct
4 Correct 52 ms 65132 KB Output is correct
5 Correct 45 ms 65404 KB Output is correct
6 Correct 36 ms 65276 KB Output is correct
7 Correct 34 ms 65352 KB Output is correct
8 Correct 34 ms 65144 KB Output is correct
9 Correct 34 ms 65208 KB Output is correct
10 Correct 34 ms 65260 KB Output is correct
11 Correct 34 ms 65172 KB Output is correct
12 Correct 37 ms 65464 KB Output is correct
13 Correct 72 ms 65792 KB Output is correct
14 Correct 98 ms 65852 KB Output is correct
15 Correct 86 ms 65744 KB Output is correct
16 Runtime error 988 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 32 ms 65228 KB Output is correct
2 Correct 30 ms 65196 KB Output is correct
3 Correct 30 ms 65176 KB Output is correct
4 Correct 54 ms 65456 KB Output is correct
5 Correct 82 ms 65288 KB Output is correct
6 Correct 34 ms 65396 KB Output is correct
7 Correct 34 ms 65404 KB Output is correct
8 Correct 39 ms 65800 KB Output is correct
9 Correct 476 ms 120640 KB Output is correct
10 Runtime error 2694 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -