oj.uz

Submission #884760

# Submission time Handle Problem Language Result Execution time Memory
884760 2023-12-08T11:30:18 Z nima_aryan Railway (BOI17_railway) C++17
36 / 100
 157 ms 26312 KB 
#include <bits/stdc++.h>

using namespace std;

class Tree {
 public:
  int n;
  vector<vector<int>> adj;
  vector<vector<int>> up;
  vector<int> dep;
  vector<int> tin;
  vector<int> tout;

  Tree(int n) : n(n) {
    adj.resize(n);
    up.resize(n);
    dep.resize(n);
    tin.resize(n);
    tout.resize(n);
  }

  void add_edge(int x, int y) {
    adj[x].push_back(y);
    adj[y].push_back(x);
  }

  void dfs(int x, int p) {
    static int T = 0;
    tin[x] = T++;
    up[x].resize(20);
    up[x][0] = p;
    for (int i = 1; i < 20; ++i) {
      up[x][i] = up[up[x][i - 1]][i - 1];
    }
    for (int y : adj[x]) {
      if (y != p) {
        dep[y] = dep[x] + 1;
        dfs(y, x);
      }
    }
    tout[x] = T;
  }
  void work() {
    dfs(0, 0);
  }

  void jump(int& at, int k) {
    for (int i = 0; i < 20; ++i) {
      if (k >> i & 1) {
        at = up[at][i];
      }
    }
  }
  int lca(int x, int y) {
    if (dep[x] < dep[y]) {
      swap(x, y);
    }
    jump(x, dep[x] - dep[y]);
    if (x == y) {
      return x;
    }
    for (int i = 20 - 1; i >= 0; --i) {
      int new_x = up[x][i];
      int new_y = up[y][i];
      if (new_x != new_y) {
        x = new_x;
        y = new_y;
      }
    }
    return up[x][0];
  }
  bool anc(int x, int y) {
    return tin[x] <= tin[y] && tout[y] <= tout[x];
  }
};

int main() {
  int n, m, k;
  cin >> n >> m >> k;

  Tree t(n);
  vector<pair<int, int>> e;
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    t.add_edge(a, b);
    e.emplace_back(a, b);
  }
  t.work();
  
  vector<int> id(n);
  for (int i = 0; i < n - 1; ++i) {
    auto [x, y] = e[i];
    if (t.dep[x] > t.dep[y]) {
      swap(x, y);
    }
    id[y] = i;
  }

  vector<int> val(n);
  while (m--) {
    int s;
    cin >> s;
    vector<int> a(s);
    for (int i = 0; i < s; ++i) {
      cin >> a[i];
      --a[i];
    }
    sort(a.begin(), a.end(), [&](int x, int y) {
      return t.tin[x] < t.tin[y];
    });
    for (int i = 1; i < s; ++i) {
      a.push_back(t.lca(a[i - 1], a[i]));
    }
    sort(a.begin(), a.end(), [&](int x, int y) {
      return t.tin[x] < t.tin[y];
    });
    a.resize(unique(a.begin(), a.end()) - a.begin());
    for (int i = 1; i < a.size(); ++i) {
      val[t.lca(a[i - 1], a[i])] -= 1;
      val[a[i]] += 1;
    }
  }
  auto dfs = [&](auto self, int x, int p) -> void {
    for (int y : t.adj[x]) {
      if (y != p) {
        self(self, y, x);
        val[x] += val[y];
      }
    }
  };
  dfs(dfs, 0, -1);
  vector<int> ans;
  for (int x = 0; x < n; ++x) {
    if (val[x] >= k) {
      ans.push_back(id[x]);
    }
  }
  cout << ans.size() << endl;
  for (int x : ans) {
    cout << x + 1 << " ";
  }
}

Compilation message

railway.cpp: In function 'int main()':
railway.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 1; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 25992 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 132 ms 25544 KB Output is correct
4 Correct 136 ms 24836 KB Output is correct
5 Correct 139 ms 26052 KB Output is correct
6 Correct 135 ms 26312 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 22688 KB Output is correct
2 Correct 122 ms 20728 KB Output is correct
3 Correct 114 ms 20500 KB Output is correct
4 Correct 127 ms 20420 KB Output is correct
5 Correct 157 ms 20420 KB Output is correct
6 Correct 120 ms 22828 KB Output is correct
7 Correct 116 ms 22740 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 22688 KB Output is correct
2 Correct 122 ms 20728 KB Output is correct
3 Correct 114 ms 20500 KB Output is correct
4 Correct 127 ms 20420 KB Output is correct
5 Correct 157 ms 20420 KB Output is correct
6 Correct 120 ms 22828 KB Output is correct
7 Correct 116 ms 22740 KB Output is correct
8 Correct 133 ms 22692 KB Output is correct
9 Correct 134 ms 22728 KB Output is correct
10 Correct 142 ms 26208 KB Output is correct
11 Correct 133 ms 26308 KB Output is correct
12 Incorrect 128 ms 20680 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -