Submission #472630

#	Time	Username	Problem	Language	Result	Execution time	Memory
472630		elgamalsalman	Railway (BOI17_railway)	C++14	0 / 100	547 ms	524292 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

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

int bordersCount[100050], n, m, k, subTreeSizes[100050];
vi ans;
vvii adj;
vvi borders;
vector<map<int, int>> currBorders;

int dfsSizes(int u, int p) {
  subTreeSizes[u] = 1;
  for (ii v : adj[u]) if (v.fi != p) {
    dfsSizes(v.fi, u);
    subTreeSizes[u] += subTreeSizes[v.fi];
  }
}

bool dfs(int u, int p) {
  for (ii v : adj[u]) if (v.fi != p) {
    if (dfs(v.fi, u)) ans.push_back(v.se);
  }

  int maxSize = 0, biggestChild = -1;
  for (ii v : adj[u]) if (v.fi != p) {
    int childSize = subTreeSizes[v.fi];
    if (childSize > maxSize) {
      maxSize = childSize;
      biggestChild = v.fi;
    }
  }

  if (biggestChild != -1) { 
    vi bordersToErase;
    swap(currBorders[biggestChild], currBorders[u]);
    for (ii currBorder : currBorders[biggestChild]) {
      currBorders[u][currBorder.fi] += currBorder.se;
      if (currBorders[u][currBorder.fi] >= bordersCount[currBorder.fi]) bordersToErase.push_back(currBorder.fi);
    }

    for (ii v : adj[u]) if (v.fi != p && v.fi != biggestChild) {
      for (ii currBorder : currBorders[v.fi]) {
	currBorders[u][currBorder.fi] += currBorder.se;
	if (currBorders[u][currBorder.fi] >= bordersCount[currBorder.fi]) bordersToErase.push_back(currBorder.fi);
      }
    }

    for (int b : bordersToErase) currBorders[u].erase(b);
  }

  int needCount = currBorders[u].size();
  //cerr << "// needCount of " << u << " : " << needCount << '\n';
  return (needCount >= k);
}

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

  cin >> n >> m >> k;
  adj.assign(n + 20, vii());
  borders.assign(n + 20, vi());
  currBorders.assign(n + 20, map<int, int>());
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    adj[u].push_back({v, i});
    adj[v].push_back({u, i});
  }

  for (int i = 0; i < m; i++) {
    cin >> bordersCount[i];
    //for (int j = 0; j < bordersCount[i]; j++) borders[j].push_back(i);
    for (int j = 0; j < bordersCount[i]; j++) {
      int borderV; cin >> borderV; borderV--;
      currBorders[borderV][i]++;
    }
  }

  dfsSizes(0, -1);
  dfs(0, -1);

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

Compilation message (stderr)

railway.cpp: In function 'int dfsSizes(int, int)':
railway.cpp:27:1: warning: no return statement in function returning non-void [-Wreturn-type]
   27 | }
      | ^

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