Submission #486086

#	Time	Username	Problem	Language	Result	Execution time	Memory
486086		Koosha_mv	Railway (BOI17_railway)	C++14	100 / 100	432 ms	79460 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define print(v,r) f(i,0,r) cout<<v[i]<<" "; cout<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define Add(x,y) x=(x+y)%mod
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=1e6+99;

int n,m,res,k,a[N],sz[N],cnt[N];
vector<int> v[N],g[N];
vector<pair<int,int> > ans;
map<int,int> mark;
map<pair<int,int>,int> edge;

void dfssz(int x,int par){
	sz[x]=1;
	f(i,0,g[x].size()){
		if(g[x][i]!=par){
			dfssz(g[x][i],x);
			sz[x]+=sz[g[x][i]];
		}
	}
}
void dfs1(int x,int par,int fbd){
	f(j,0,v[x].size()){
		mark[v[x][j]]++;
		if(mark[v[x][j]]==cnt[v[x][j]]){
			res++;
		}
	}
	f(i,0,g[x].size()){
		if(g[x][i]!=par && g[x][i]!=fbd){
			dfs1(g[x][i],x,fbd);
		}
	}
}
void dfs(int x,int par){
	int u=0;
	f(i,0,g[x].size()){
		if(g[x][i]!=par && sz[g[x][i]]>sz[u]){
			u=g[x][i];
		}
	}
	f(i,0,g[x].size()){
		if(g[x][i]!=par && g[x][i]!=u){
			dfs(g[x][i],x);
		}
	}
	mark.clear();
	res=0;
	if(u>0){
		dfs(u,x);
	}
	dfs1(x,par,u);
	//cout<<x<<" : "<<mark.size()<<endl;
	//cout<<x<<" : "<<endl;
	//for(auto u : mark){
	//   cout<<u.F<<" "<<u.S<<endl;
	//}
	//cout<<mark.size()<<endl;
	//cout<<endl;
	if(mark.size()-res>=k){
		ans.pb(mp(x,par));
	}
}

int main(){
	cin>>n>>m>>k;
	f(i,1,n){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
		edge[mp(u,v)]=i;
		edge[mp(v,u)]=i;
	}
	f(i,0,m){
		int x;
		cin>>cnt[i];
		f(j,0,cnt[i]){
			cin>>x;
			v[x].pb(i);
		}
	}
	dfssz(1,0);
	dfs(1,0);
	vector<int> v;
	cout<<ans.size()<<endl;
	f(i,0,ans.size()){
		v.pb(edge[mp(ans[i].F,ans[i].S)]);
	}
	sort(v.begin(),v.end());
	f(i,0,v.size()) cout<<v[i]<<" ";
}
/*
6 3 2
1 3
2 3
3 4
6 4
4 5
4 1 3 2 5
2 6 3
2 3 2
*/

Compilation message (stderr)

railway.cpp: In function 'void dfssz(int, int)':
railway.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   30 |  f(i,0,g[x].size()){
      |    ~~~~~~~~~~~~~~~             
railway.cpp:30:2: note: in expansion of macro 'f'
   30 |  f(i,0,g[x].size()){
      |  ^
railway.cpp: In function 'void dfs1(int, int, int)':
railway.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   38 |  f(j,0,v[x].size()){
      |    ~~~~~~~~~~~~~~~             
railway.cpp:38:2: note: in expansion of macro 'f'
   38 |  f(j,0,v[x].size()){
      |  ^
railway.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   44 |  f(i,0,g[x].size()){
      |    ~~~~~~~~~~~~~~~             
railway.cpp:44:2: note: in expansion of macro 'f'
   44 |  f(i,0,g[x].size()){
      |  ^
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   52 |  f(i,0,g[x].size()){
      |    ~~~~~~~~~~~~~~~             
railway.cpp:52:2: note: in expansion of macro 'f'
   52 |  f(i,0,g[x].size()){
      |  ^
railway.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   57 |  f(i,0,g[x].size()){
      |    ~~~~~~~~~~~~~~~             
railway.cpp:57:2: note: in expansion of macro 'f'
   57 |  f(i,0,g[x].size()){
      |  ^
railway.cpp:75:20: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |  if(mark.size()-res>=k){
      |     ~~~~~~~~~~~~~~~^~~
railway.cpp: In function 'int main()':
railway.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
  102 |  f(i,0,ans.size()){
      |    ~~~~~~~~~~~~~~              
railway.cpp:102:2: note: in expansion of macro 'f'
  102 |  f(i,0,ans.size()){
      |  ^
railway.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
  106 |  f(i,0,v.size()) cout<<v[i]<<" ";
      |    ~~~~~~~~~~~~                
railway.cpp:106:2: note: in expansion of macro 'f'
  106 |  f(i,0,v.size()) cout<<v[i]<<" ";
      |  ^

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