Submission #472396

#	Time	Username	Problem	Language	Result	Execution time	Memory
472396		elgamalsalman	Railway (BOI17_railway)	C++14	0 / 100	61 ms	16876 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

int n, m, k, markCount[100050], newInds[100050], pSum[100050], returnInd[100050];
vvii adj;
vii edges;
bitset<100050> visited, isDest;

void dfs(int u, int ind) {
  //cerr << "// dfs(" << u << ", " << ind << ")\n";
  if (newInds[u] != -1) return;
  newInds[u] = ind;
  returnInd[ind] = u;
  for (ii edge : adj[u]) dfs(edge.fi, ind + 1);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

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

  int globalStart = 0;
  for (int i = 0; i < n; i++) {
    if (adj[i].size() == 1) globalStart = i;
  }
  //globalStart = 1;

  memset(newInds, -1, sizeof newInds);
  dfs(globalStart, 0);

  //for (int i = 0; i < n; i++) cerr << "// " << i << " became " << newInds[i] << '\n';

  for (int j = 0; j < m; j++) {
    int s;
    cin >> s;
    int minS = 1e9, maxS = 0;
    for (int i = 0; i < s; i++) {
      int tmp; cin >> tmp;
      minS = min(minS, newInds[tmp]);
      maxS = max(maxS, newInds[tmp]);
    } 
    //cerr << "// minS : " << minS << '\n';
    //cerr << "// maxS : " << maxS << '\n';
    pSum[minS + 1]++;
    pSum[maxS + 1]--;
  }

  for (int i = 1; i < 100050; i++) pSum[i] += pSum[i - 1];

  //for (int i = 0; i < n; i++) cerr << "// pSum[" << i << "] : " << pSum[i] << '\n';

  vi ans;
  for (int i = 0; i < n - 1; i++) {
    if (pSum[i] >= k) ans.push_back(returnInd[i]);
  }

  cout << (int)ans.size() << '\n';
  for (int i = 0; i < (int)ans.size(); i++) {
    if (i) cout << ' ';
    cout << ans[i] + 1;
  }
  cout << '\n';
}

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