Submission #972292

#	Time	Username	Problem	Language	Result	Execution time	Memory
972292		Dzadzo	Railway (BOI17_railway)	C++17	52 / 100	127 ms	35960 KiB

railway

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000007
#define MAXN 100000
using namespace std;
int s[MAXN+1],k;
vvp adj(MAXN+1);
vvi X(MAXN+1);
vi dp(MAXN+1);
map <int,int> *cnt[MAXN+1];
vi ans;
void dfs(int v,int p,int q){
	pii best={-1,-1};
	for (auto &[to,Q]:adj[v]){
		if (to==p)continue;
		dfs(to,v,Q);
		dp[v]+=dp[to];
		best=max(best,{(*cnt[to]).size(),to});
	}
	if (best.S!=-1)cnt[v]=cnt[best.S];else cnt[v]=new map<int,int>();
	for (int x:X[v]){
		(*cnt[v])[x]++;
		if ((*cnt[v])[x]==s[x])dp[v]++;
	}
	for (auto &[to,Q]:adj[v]){
		if (to==p || to==best.S)continue;
		for (auto &[id,x]:*cnt[to]){
			(*cnt[v])[id]+=x;
			if ((*cnt[v])[id]==s[id])dp[v]++;
		}
	}
	if (dp[v]+k<=(*cnt[v]).size())ans.pb(q);
}
signed main(){	
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,m;
	cin>>n>>m>>k;
	for (int i=1,u,v;i<n;i++){
		cin>>u>>v;
		adj[u].pb({v,i});
		adj[v].pb({u,i});
	}
	for (int i=1;i<=m;i++){
		cin>>s[i];
		for (int j=1,c;j<=s[i];j++){
			cin>>c;
			X[c].pb(i);
		}
	}
	dfs(1,0,0);
	cout<<ans.size()<<"\n";
	sort(ans.begin(),ans.end());
	for (int x:ans)cout<<x<<" ";
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(long long int, long long int, long long int)':
railway.cpp:45:13: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  if (dp[v]+k<=(*cnt[v]).size())ans.pb(q);

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