Submission #556129

#	Time	Username	Problem	Language	Result	Execution time	Memory
556129		MilosMilutinovic	Railway (BOI17_railway)	C++14	100 / 100	135 ms	24992 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int L=20;
int n,m,k,par[N][L],dep[N],a[N],f[N],lid[N],rid[N],tid,x[N],y[N];
vector<int> E[N];
void DFS(int u,int p){
	lid[u]=++tid;
	dep[u]=dep[p]+1;
	par[u][0]=p;
	for(int j=1;j<L;j++)par[u][j]=par[par[u][j-1]][j-1];
	for(int v:E[u])if(v!=p)DFS(v,u);
	rid[u]=tid;
}
int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=L-1;~i;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i];
	for(int i=L-1;~i;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
	return u==v?v:par[u][0];
}
void Solve(int u,int p){
	for(int v:E[u])if(v!=p)Solve(v,u),f[u]+=f[v];
}
int main(){
	scanf("%i%i%i",&n,&m,&k);
	for(int i=1;i<n;i++){
		scanf("%i%i",&x[i],&y[i]);
		E[x[i]].pb(y[i]);
		E[y[i]].pb(x[i]);
	}
	DFS(1,0);
	while(m--){
		int s;scanf("%i",&s);
		for(int i=1;i<=s;i++)scanf("%i",&a[i]);
		sort(a+1,a+1+s,[&](int i,int j){return lid[i]<lid[j];});
		a[++s]=a[1];
		for(int i=1;i<s;i++){
			f[a[i]]++;
			f[a[i+1]]++;
			f[LCA(a[i],a[i+1])]-=2;
		}
	}
	Solve(1,0);
	vector<int> ans;
	for(int i=1;i<n;i++){
		if(dep[x[i]]<dep[y[i]])swap(x[i],y[i]);
		if(f[x[i]]>=2*k)ans.pb(i);
	}
	printf("%i\n",ans.size());
	for(int i=0;i<ans.size();i++)printf("%i ",ans[i]);
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:50:11: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   50 |  printf("%i\n",ans.size());
      |          ~^    ~~~~~~~~~~
      |           |            |
      |           int          std::vector<int>::size_type {aka long unsigned int}
      |          %li
railway.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<ans.size();i++)printf("%i ",ans[i]);
      |              ~^~~~~~~~~~~
railway.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%i%i%i",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
railway.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%i%i",&x[i],&y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
railway.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   int s;scanf("%i",&s);
      |         ~~~~~^~~~~~~~~
railway.cpp:35:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   for(int i=1;i<=s;i++)scanf("%i",&a[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