제출 #472628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472628		elgamalsalman	Railway (BOI17_railway)	C++14	23 / 100	1095 ms	309404 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);
  }

  vi bordersToErase;
  for (ii v : adj[u]) if (v.fi != p) {
    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, vii());
  borders.assign(n, vi());
  currBorders.assign(n, 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';
}

컴파일 시 표준 에러 (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: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25