Submission #552854

#	Time	Username	Problem	Language	Result	Execution time	Memory
552854		_Avocado_	Railway (BOI17_railway)	C++14	100 / 100	183 ms	43748 KiB

railway

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

vector<vector<int>>graph;
vector<unordered_map<int, int>>col;
vector<int>ans, tot, par;

int n, m, k;

void dfs(int v, int p){
	par[v] = p;
	for(auto u: graph[v]){
		if(u != p){
			dfs(u, v);
			if(col[u].size() > col[v].size()) swap(col[u], col[v]);
			for(auto [key, val] : col[u]){
				col[v][key] += val;
				if(col[v][key] == tot[key]){
					col[v].erase(key);
				}
			}
		}
	}
	
	if(col[v].size() >= k) ans[v] = 1;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin ("input.in");
	//ofstream cout ("output.out");
	
	cin>>n>>m>>k;
	
	graph.assign(n, vector<int>());
	col.assign(n, unordered_map<int, int>());
	ans.assign(n, 0);
	par.assign(n, 0);
	vector<pair<int, int>>input;
	
	for(int i = 0; i<n-1; ++i){
		int a, b; cin>>a>>b;
		--a; --b;
		graph[a].push_back(b);
		graph[b].push_back(a);
		input.push_back({a, b});
	}
	
	tot.assign(m, 0);
	
	for(int i = 0; i<m; ++i){
		int s; cin>>s;
		tot[i] = s;
		for(int j = 0; j<s; ++j){
			int a; cin>>a;
			--a;
			++col[a][i];
		}
	}

	dfs(0, 0);
	
	vector<int>fred;
	
	for(int i = 0; i<n-1; ++i){
		int a = input[i].first;
		int b = input[i].second;
		if(par[a] == b && ans[a]) fred.push_back(i+1);
		else if(par[b] == a && ans[b]) fred.push_back(i+1);
	}
	
	cout<<fred.size()<<'\n';
	for(auto u: fred) cout<<u<<" ";
	
	
	cout<<'\n';
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int64_t, int64_t)':
railway.cpp:17:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |    for(auto [key, val] : col[u]){
      |             ^
railway.cpp:26:19: warning: comparison of integer expressions of different signedness: 'std::unordered_map<long int, long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   26 |  if(col[v].size() >= k) ans[v] = 1;
      |     ~~~~~~~~~~~~~~^~~~

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