Submission #419717

#	Time	Username	Problem	Language	Result	Execution time	Memory
419717		victoriad	Railway (BOI17_railway)	C++14	23 / 100	1093 ms	20244 KiB

railway

#include <cmath>
#include <cstdio>
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;

void dfs(int i,vector<int>&depth,vector<int>&parent,vector<vector<int> >&a,vector<bool>&v,int p){
	v[i]=true;
	depth[i]=1+depth[p];
	parent[i]=p;
	for(int c:a[i]){
		if(!v[c])
		dfs(c,depth,parent,a,v,i);
	}
}

int ide(int a,int b,vector<vector<pair<int,int> > >&ref){
	if(b<a)swap(a,b);
	int low=0,hi=ref[a].size()-1,m,r;
	while(low<=hi){
		int m=low+(hi-low)/2;
		if(ref[a][m].first<=b){
			low=m+1;
			r=m;
		}
		else{
			hi=m-1;
		}
	}
	return ref[a][r].second;
}

void conectar(int a,int b,vector<int>&d,vector<int>&p,vector<int>&con,int k,vector<int>&r,vector<vector<pair<int,int> > >&ref,vector<bool>&v){
	if(d[a]<d[b])swap(a,b);
	while(d[a]!=d[b]){
		int pa=p[a];
		int id=ide(pa,a,ref);
		if(!v[id]){
		con[id]++;
		v[id]=true;
		if(con[id]==k){
			r.push_back(id);
		}
		}
		a=pa;
	}
	while(a!=b){
		int pa=p[a];
		int pb=p[b];
		int id=ide(pa,a,ref);
		if(!v[id]){
		con[id]++;
		v[id]=true;
		if(con[id]==k && pa!=a){
			r.push_back(id);
		}
		}
		id=ide(pb,b,ref);
		if(!v[id]){
		con[id]++;
		v[id]=true;
		if(con[id]==k && pa!=a){
			r.push_back(id);
		}
		}
		a=pa;
		b=pb;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,k,m,x,y,j;
	cin>>n>>m>>k;
	vector<vector<pair<int,int> > >ref(n);
	vector<vector<int> >a(n);
	for(int i=0;i<n-1;i++){
		cin>>x>>y;
		x--;
		y--;
		if(x>y)swap(x,y);
		ref[x].push_back(make_pair(y,i+1));
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(int i=0;i<n;i++){
		sort(ref[i].begin(),ref[i].end());
	}
	vector<int>depth(n,0);
	vector<int>parent(n,0);
	vector<bool>v(n,false);
	dfs(0,depth,parent,a,v,0);
	vector<int>con(n+1,0);
	vector<int>r;
	for(int i=0;i<m;i++){
		cin>>j;
		cin>>x;
		x--;
		v.assign(n+1,false);
		for(int o=1;o<j;o++){
			cin>>y;
			y--;
			conectar(x,y,depth,parent,con,k,r,ref,v);
			y=x;
		}
	}
	sort(r.begin(),r.end());
	cout<<r.size()<<"\n";
	for(int i=0;i<r.size();i++){
		cout<<r[i]<<" ";
	}

	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int ide(int, int, std::vector<std::vector<std::pair<int, int> > >&)':
railway.cpp:22:31: warning: unused variable 'm' [-Wunused-variable]
   22 |  int low=0,hi=ref[a].size()-1,m,r;
      |                               ^
railway.cpp: In function 'int main()':
railway.cpp:113:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~
railway.cpp: In function 'int ide(int, int, std::vector<std::vector<std::pair<int, int> > >&)':
railway.cpp:33:17: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |  return ref[a][r].second;
      |                 ^

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