Submission #647529

#	Time	Username	Problem	Language	Result	Execution time	Memory
647529		ymm	Railway (BOI17_railway)	C++17	100 / 100	139 ms	38388 KiB

railway

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
vector<int> cols[N];
vector<pii> A[N];
int col_cnt[N];
int n, m, k;

class s2l {
private:
	int cnt_unfin = 0;
	map<int, int> mp;
public:
	void insert(int x, int cnt=1)
	{
		int &val = mp[x];
		cnt_unfin += val == 0;
		val += cnt;
		cnt_unfin -= val == col_cnt[x];
	}
	void merge(s2l *that)
	{
		if (mp.size() < that->mp.size()) {
			mp.swap(that->mp);
			swap(cnt_unfin, that->cnt_unfin);
		}
		for (auto [x, y] : that->mp)
			insert(x, y);
		delete(that);
	}
	int get_cnt()
	{
		return cnt_unfin;
	}
};

vector<int> ans_edges;

s2l *dfs(int v, int p)
{
	s2l *ans = new s2l;
	for (int c : cols[v])
		ans->insert(c);
	for (auto [u, e] : A[v]) {
		if (e == p)
			continue;
		ans->merge(dfs(u, e));
	}
	if (p != -1 && ans->get_cnt() >= k)
		ans_edges.push_back(p);
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m >> k;
	Loop (i,0,n-1) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back({u,i});
		A[u].push_back({v,i});
	}
	Loop (i,0,m) {
		cin >> col_cnt[i];
		Loop (j,0,col_cnt[i]) {
			int v;
			cin >> v;
			cols[v-1].push_back(i);
		}
	}
	dfs(0, -1);
	sort(ans_edges.begin(), ans_edges.end());
	cout << ans_edges.size() << '\n';
	for (int e : ans_edges)
		cout << e+1 << ' ';
	cout << '\n';
}

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