Submission #757738

#	Time	Username	Problem	Language	Result	Execution time	Memory
757738		SteGG	Railway (BOI17_railway)	C++17	100 / 100	155 ms	43652 KiB

railway

//Judges with GCC >= 12 only needs Ofast
//#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
//MLE optimization
//#pragma GCC optimize("conserve-stack")
//Old judges
//#pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
//New judges. Test with assert(__builtin_cpu_supports("avx2"));
//#pragma GCC target("arch=skylake")
//Atcoder
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//write variables and debug
#define bugf cout << "Here" << endl
#define bug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define bugarr(arr,...) cout << #arr; _dbg_arr(arr, __VA_ARGS__)

template <class T>
ostream& operator<<(ostream& output, const vector<T> &arr){
	int n = arr.size();
	output << "[";
	for(int i = 0; i < n; i++){
		output << arr[i];
		if(i != n - 1) output << ", ";
	}
	output << "]";
	return output;
}

template<class T, class U>
ostream& operator<<(ostream& output, const pair<T, U> &A){
	output << "(" << A.first << ", " << A.second <<  ")";
	return output;
}

template<class T>
ostream& operator<<(ostream& output, const set<T> &s){
	output << "{";
	for(auto it = s.begin(); it != s.end(); it++){
		if(it != s.begin()) output << ", ";
		output << (*it);
	}
	output << "}";
	return output;
}

template<class T, class U>
ostream& operator<<(ostream& output, const map<T, U> &m){
	output << "{";
	for(auto it = m.begin(); it != m.end(); it++){
		if(it != m.begin()) output << ", ";
		output << "(" << it->first << " : " << it->second << ")";
	}
	output << "}";
	return output;
}

template<class TH>
void _dbg(const char *sdbg, TH h){
	cout << sdbg << " = " << h << endl;
}

template<class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
	while(*sdbg != ',')cout << *sdbg++;
	cout << " = " << h << "\n";
	_dbg(sdbg+1, a...);
}

template<class _Arr, class _Index>
void _dbg_arr(_Arr arr, _Index index){
	cout << '[' << index << "] = " << arr[index] << endl;
}

template<class _Arr, class _Index, class... TA>
void _dbg_arr(_Arr &arr, _Index index, TA... args){
	cout << '[' << index << ']';
	_dbg_arr(arr[index], args...);
}

//open file
#define taskname "" //name input and output file

#ifdef SteGG
void open(){
	if(fopen("input.inp", "r")){
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	}
}
#else
void open(){
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
}
#endif

//initialize
#define testcase \
	long long test; \
	cin >> test; \
	for(int tst = 1; tst <= test; tst++)
#define int long long
#define MOD 1000000007
#define FFTMOD (119 << 23 | 1)
#define EPSILON 1e-9
#define setpre(x) fixed << setprecision(x)
#define cd complex<double>
#define all(x) x.begin(), x.end()
#define endl '\n'

const long long INF = 3e18L + 5;
const int inf = 1e9 + 7;
const double infd = 1e60;
const double PI = acos(-1);
const int maxn = 1e5 + 5;
//const int base = ;
int n, m, k;
vector<int> id_edges[maxn];
int sz_query[maxn];
vector<int> id_query[maxn];
unordered_map<int, int> *sus[maxn];
int finished[maxn];
vector<int> result;

//others struct or class

struct Edge{
	int u, v;
	Edge() : u(0), v(0) {}
	Edge(int _u, int _v) : u(_u), v(_v) {}
	int get(int _u){
		if(_u == u) return v;
		else return u;
	}
};

//others function

//others init

Edge edges[maxn];

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	open();
	cin >> n >> m >> k;
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		edges[i] = Edge(u, v);
		id_edges[u].push_back(i);
		id_edges[v].push_back(i);
	}

	for(int i = 1; i <= m; i++){
		int sz;
		cin >> sz;
		sz_query[i] = sz;
		for(int j = 1; j <= sz; j++){
			int u;
			cin >> u;
			id_query[u].push_back(i);
		}
	}	

	function<int(int, int, int)> dfs = [&](int u, int p, int cur_id) -> int {
		int sz_subtree = 1;
		vector<int> children;
		int largest = -1;
		int max_sz = 0;
		for(int id : id_edges[u]){
			int v = edges[id].get(u);
			if(v == p) continue;
			children.push_back(v);
			int temp = dfs(v, u, id);
			if(largest == -1 || max_sz < temp){
				max_sz = temp;
				largest = v;
			}
			sz_subtree += temp;
		}

		if(largest == -1){
			sus[u] = new unordered_map<int, int>();
			finished[u] = 0;
		}else{
			sus[u] = sus[largest];
			finished[u] = finished[largest];
		}


		for(int child : children){
			if(child == largest) continue;
			for(auto it = sus[child]->begin(); it != sus[child]->end(); it++){
				int id_q = it->first;
				int cnt = it->second;
				(*sus[u])[id_q] += cnt;
				if((*sus[u])[id_q] == sz_query[id_q]) finished[u]++;
			}
		}

		for(int id_q : id_query[u]){
			(*sus[u])[id_q]++;
			if((*sus[u])[id_q] == sz_query[id_q]) finished[u]++;
		}

		if(sus[u]->size() - finished[u] >= k) result.push_back(cur_id);
		return sz_subtree;
	};

	dfs(1, 0, -1);

	sort(all(result));

	cout << result.size() << endl;
	for(int i = 0; i < result.size(); i++){
		cout << result[i];
		if(i != result.size() - 1) cout << " ";
		else cout << endl;
	}

	return 0;
}

Compilation message (stderr)

railway.cpp: In lambda function:
railway.cpp:219:35: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
  219 |   if(sus[u]->size() - finished[u] >= k) result.push_back(cur_id);
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
railway.cpp: In function 'int main()':
railway.cpp:228:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  228 |  for(int i = 0; i < result.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
railway.cpp:230:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |   if(i != result.size() - 1) cout << " ";
      |      ~~^~~~~~~~~~~~~~~~~~~~
railway.cpp: In function 'void open()':
railway.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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