Submission #1115804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115804		vjudge1	Railway (BOI17_railway)	C++17	100 / 100	84 ms	25032 KiB

railway

#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 1e5;

int n, m, k, t = 0, u[NM+5], v[NM+5], st[NM+5], en[NM+5];
vector <int> adj[NM+5], s[NM+5];
vector <pii> A;
int vertex_id[NM+5], edge_id[NM+5], set_id[NM+5];
int bit[NM+5], f[NM+5], ptr[NM+5], g[NM+5];
vector <int> ans;

void DFS(int u, int p){
	st[u] = ++t;
	for (int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i];
		if (v == p) continue;
		DFS(v, u);
	}
	en[u] = t;
}

bool vertex_cmp(int x, int y){
	return st[x] < st[y];
}

bool set_cmp(int x, int y){
	return st[s[x][0]] < st[s[y][0]];
}

bool other_cmp(pii a, pii b){
	return st[a.fi] < st[b.fi];
}

void update(int p, int v){
	while (p <= n){
		bit[p] += v;
		p += p & (-p);
	}
}

int get(int p){
	int res = 0;
	while (p > 0){
		res += bit[p];
		p -= p & (-p);
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++){
		cin >> u[i] >> v[i];
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
		vertex_id[i+1] = i+1;
	}
	DFS(1, -1);
	sort(vertex_id+2, vertex_id+1+n, vertex_cmp);
	for (int i = 1; i <= m; i++){
		int t, v; cin >> t;
		while (t--){
			cin >> v;
			s[i].push_back(v);
			A.push_back(mp(v, i));
		}
		sort(s[i].begin(), s[i].end(), vertex_cmp);
		set_id[i] = i;
	}
	sort(set_id+1, set_id+1+m, set_cmp);
	int j = m;
	for (int ii = n; ii >= 2; ii--){
		int i = vertex_id[ii];
		while (j >= 1 && st[s[set_id[j]][0]] >= st[i]){
			update(st[s[set_id[j]].back()], 1);
			j--;
		}
		f[i] = m-get(en[i]);
	}
	sort(A.begin(), A.end(), other_cmp);
	for (int i = 1; i <= m; i++) ptr[i] = s[i].size();
	memset(bit, 0, sizeof(bit));
	j = A.size()-1;
	for (int ii = n; ii >= 2; ii--){
		int i = vertex_id[ii];
		while (j >= 0 && st[A[j].fi] >= st[i]){
			if (ptr[A[j].se] < s[A[j].se].size()) update(st[s[A[j].se][ptr[A[j].se]]], -1);
			ptr[A[j].se]--;
			if (ptr[A[j].se] >= 0) update(st[A[j].fi], 1);
			j--;
		}
		g[i] = get(en[i]);
	}
	for (int i = 1; i < n; i++){
		if (st[u[i]] > st[v[i]]) swap(u[i], v[i]);
		if (f[v[i]]+g[v[i]]-m >= k) ans.push_back(i);
	}
	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void DFS(int, int)':
railway.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (int i = 0; i < adj[u].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    if (ptr[A[j].se] < s[A[j].se].size()) update(st[s[A[j].se][ptr[A[j].se]]], -1);
      |        ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
railway.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for (int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
      |                  ~~^~~~~~~~~~~~

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