Submission #552740

#	Time	Username	Problem	Language	Result	Execution time	Memory
552740		_Avocado_	Railway (BOI17_railway)	C++14	100 / 100	214 ms	48376 KiB

railway

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

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

int n, m, k;

void direct(int v, int p){
	par[v] = p;
	for(auto u: graph[v]){
		if(u != p) direct(u, v);
	}
}

void dfs(int v){
	for(auto u: dgraph[v]){
		dfs(u);
		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]){
				//cout<<"helloo "<<key<<" "<<v<<endl;
				col[v].erase(key);
			}
		}
	}
	//cout<<"v "<<v<<endl;
	//for(auto [key, val]: col[v]) cout<<key<<" "<<val<<endl;
	//cout<<endl;
	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});
	}
	
	direct(0, 0);
	
	dgraph.assign(n, vector<int>());
	for(int i = 0; i<n; ++i){
		if(par[i] != i) dgraph[par[i]].push_back(i);
	}
	
	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];
		}
	}
	//for(auto u: tot) cout<<u<<" ";
	//cout<<endl;
	/*
	for(auto u: col){
		for(auto [key, val]: u) cout<<key<<" "<<val<<endl;
		cout<<endl;
	}
	*/
	

	dfs(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)':
railway.cpp:22:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |   for(auto [key, val] : col[u]){
      |            ^
railway.cpp:33: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]
   33 |  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