제출 #1284412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284412		lmquan	Railway (BOI17_railway)	C++20	100 / 100	85 ms	21840 KiB

railway

#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const int kN = 1e5 + 1;
const int kLG = 20;

int n, m, k, timer, in[kN], out[kN], jump[kLG][kN];
vector<int> adj[kN];
vector<pair<int, int>> edges;

void DFS(int u, int p) {
  in[u] = ++timer;
  jump[0][u] = p;
  for (int i = 1; i < kLG; i++) {
    jump[i][u] = jump[i - 1][jump[i - 1][u]];
  }
  for (auto v : adj[u]) {
    if (v == p) {
      continue;
    }
    DFS(v, u);
  }
  out[u] = timer;
}

bool Ancestor(int u, int v) {
  return (in[u] <= in[v] && out[v] <= out[u]);
}

int LCA(int u, int v) {
  if (Ancestor(u, v)) {
    return u;
  }
  for (int i = kLG - 1; i >= 0; i--) {
    if (jump[i][u] >= 1 && !Ancestor(jump[i][u], v)) {
      u = jump[i][u];
    }
  }
  return jump[0][u];
}

struct FenwickTree {
  int t;
  vector<int> bit;
  FenwickTree(int _t) : t(_t) {
    bit.resize(t + 1, 0);
  }
  void Update(int p, int x) {
    for (int i = p; i <= t; i += i & (-i)) {
      bit[i] += x;
    }
  }
  int PrefixSum(int p) {
    int k = 0;
    for (int i = p; i > 0; i -= i & (-i)) {
      k += bit[i];
    }
    return k;
  }

  int RangeSum(int l, int r) {
    return PrefixSum(r) - PrefixSum(l - 1);
  }
};

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m >> k;
  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    edges.push_back({a, b});
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  int root = 1;
  DFS(root, 0);
  FenwickTree a(n);
  for (int i = 1; i <= m; i++) {
    int s;
    cin >> s;
    vector<int> b;
    for (int j = 1; j <= s; j++) {
      int c;
      cin >> c;
      b.push_back(c);
    }
    sort(b.begin(), b.end(), [&](int x, int y) {
      return in[x] < in[y];
    });
    b.push_back(b[0]);
    for (int j = 0; j + 1 < b.size(); j++) {
      a.Update(in[b[j]], 1);
      a.Update(in[b[j + 1]], 1);
      a.Update(in[LCA(b[j], b[j + 1])], -2);
    }
  }

  vector<int> result;
  for (int i = 0; i < n - 1; i++) {
    if (jump[0][edges[i].first] == edges[i].second) {
      swap(edges[i].first, edges[i].second);
    }
    if (a.RangeSum(in[edges[i].second], out[edges[i].second]) >= 2 * k) {
      result.push_back(i + 1);
    }
  }
  cout << result.size() << '\n';
  for (int i : result) {
    cout << i << ' ';
  }

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'int main()':
railway.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25