제출 #697427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697427		d4xn	Railway (BOI17_railway)	C++17	36 / 100	134 ms	36268 KiB

railway

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define int long long


const int N = 1e5 + 5, L = 20;

int n, m, k, tim, dep[N], sz[N], pre[N], upId[N], f[N], up[L][N];
vector<pair<int, int>> adj[N];

void dfs(int u, int par, int id, int d) {
	dep[u] = d;
	pre[u] = tim++;
	sz[u] = 1;
	upId[u] = id;
	up[0][u] = par;
	for (auto &[v, idx] : adj[u]) {
		if (v == par) continue;
		dfs(v, u, idx, d + 1);
		sz[u] += sz[v];
	}
}

int lca(int x, int y) {
	if (dep[x] < dep[y])
		swap(x, y);
	int dif = dep[x] - dep[y];
	for (int b = 0; b < L; b++) {
		if (dif & (1 << b))
			x = up[b][x];
	}
	if (x == y)
		return x;

	for (int b = L - 1; b >= 0; b--) {
		if (up[b][x] == up[b][y])
			continue;
		x = up[b][x];
		y = up[b][y];
	}
	return up[0][x];
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m >> k;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		adj[x].push_back(make_pair(y, i));
		adj[y].push_back(make_pair(x, i));
	}
	tim = 0;
	dfs(0, 0, -1, 0);

	for (int j = 1; j < L; j++) {
		for (int i = 0; i < n; i++) {
			up[j][i] = up[j - 1][up[j - 1][i]];
		}
	}

	while (m--) {
		int x;
		cin >> x;

		set<pair<int, int>> v;
		for (int i = 0; i < x; i++) {
			int y;
			cin >> y;
			y--;
			v.insert(make_pair(pre[y], y));
		}

		set<int> tims;
		vector<pair<int, int>> ordP, ordD;

		while (!v.empty()) {
			int y = prev(v.end())->second;
			if (v.size() >= 2) {
				int z = prev(prev(v.end()))->second;
				int lc = lca(y, z);

				tims.insert(pre[y]);
				ordP.push_back(make_pair(pre[y], y));
				ordD.push_back(make_pair(dep[y], y));

				tims.insert(pre[z]);
				ordP.push_back(make_pair(pre[z], z));
				ordD.push_back(make_pair(dep[z], z));

				v.erase(make_pair(pre[y], y));
				v.erase(make_pair(pre[z], z));
				if (lc != y && lc != z) {
					v.insert(make_pair(pre[lc], lc));
				}
			}
			else {
				tims.insert(pre[y]);
				ordP.push_back(make_pair(pre[y], y));
				ordD.push_back(make_pair(dep[y], y));
				v.erase(make_pair(pre[y], y));
			}
		}
		sort(ordP.begin(), ordP.end());
		sort(ordD.rbegin(), ordD.rend());

		for (int i = 0; i < ordD.size(); i++) {
			int y = ordD[i].second;
			f[y]++;
			auto l = tims.upper_bound(pre[y]);
			
			vector<int> to_erase;
			for (; l != tims.end(); l++) {
				if (*l >= pre[y]+sz[y]) break;
				f[y]--;
				to_erase.push_back(*l);
			}
			for (int& j : to_erase) tims.erase(j);
			if (i == ordD.size()-1) f[y]--;
		}
	}

	vector<pair<int, int>> ordD(n);
	for (int i = 0; i < n; i++) {
		ordD[i] = make_pair(dep[i], i);
	}
	sort(ordD.rbegin(), ordD.rend());

  vector<int> ans;
  for (int i = 0; i < n; i++) {
    int x = ordD[i].second;
    if (f[x] >= k) ans.push_back(upId[x]);
    f[up[0][x]] += f[x];
  }
  sort(ans.begin(), ans.end());

  cout << ans.size() << "\n";
  for (int& i : ans) {
    cout << i+1 << " ";
  }
  cout << "\n";
}

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

railway.cpp: In function 'int main()':
railway.cpp:113:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for (int i = 0; i < ordD.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
railway.cpp:125:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |    if (i == ordD.size()-1) f[y]--;
      |        ~~^~~~~~~~~~~~~~~~

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