Submission #896403

#	Time	Username	Problem	Language	Result	Execution time	Memory
896403		pcc	Railway (BOI17_railway)	C++14	100 / 100	147 ms	34920 KiB

railway

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e5+10;
map<int,int> mp[mxn];
int good;
int N,M,K;
vector<pii> tree[mxn];
vector<int> req[mxn];
vector<int> ans;
int sz[mxn];

void dfs(int now,int par,int id){
	for(auto nxt:tree[now]){
		if(nxt.fs == par)continue;
		dfs(nxt.fs,now,nxt.sc);
		if(mp[nxt.fs].size()>mp[now].size())swap(mp[now],mp[nxt.fs]);
		for(auto &i:mp[nxt.fs]){
			mp[now][i.fs] += i.sc;
			if(mp[now][i.fs] == sz[i.fs])mp[now].erase(i.fs);
		}
	}
	for(auto &i:req[now]){
		mp[now][i]++;
		if(mp[now][i] == sz[i])mp[now].erase(i);
	}
	if(mp[now].size()>=K&&id)ans.push_back(id);
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>K;
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back({b,i});
		tree[b].push_back({a,i});
	}
	for(int i = 1;i<=M;i++){
		int tmp;
		cin>>tmp;
		sz[i] = tmp;
		while(tmp--){
			int k;
			cin>>k;
			req[k].push_back(i);
		}
	}
	dfs(1,0,0);
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<'\n';
	for(auto &i:ans)cout<<i<<' ';cout<<'\n';
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int, int)':
railway.cpp:35:19: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |  if(mp[now].size()>=K&&id)ans.push_back(id);
      |     ~~~~~~~~~~~~~~^~~
railway.cpp: In function 'int main()':
railway.cpp:60:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   60 |  for(auto &i:ans)cout<<i<<' ';cout<<'\n';
      |  ^~~
railway.cpp:60:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   60 |  for(auto &i:ans)cout<<i<<' ';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