Submission #884762

#	Time	Username	Problem	Language	Result	Execution time	Memory
884762		nima_aryan	Railway (BOI17_railway)	C++17	0 / 100	166 ms	25884 KiB

railway

#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 = 1; x < n; ++x) {
    if (val[x] >= k) {
      ans.push_back(id[x]);
    }
  }
  cout << ans.size() << "\n";
  for (int x : ans) {
    cout << x + 1;
  }
  cout << "\n";
}

Compilation message (stderr)

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25