Submission #419692

#	Time	Username	Problem	Language	Result	Execution time	Memory
419692		victoriad	Railway (BOI17_railway)	C++14	0 / 100	1092 ms	16864 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<pair<int,int> >&ref){
	int i=0;
	for(i;i<ref.size();i++){
		if((ref[i].first==a && ref[i].second==b )||(ref[i].first==b && ref[i].second==a ))break;
	}
	return i+1;
}

void conectar(int a,int b,vector<int>&d,vector<int>&p,vector<int>&con,int k,vector<int>&r,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<pair<int,int> >ref(n);
	vector<vector<int> >a(n);
	for(int i=0;i<n-1;i++){
		cin>>x>>y;
		x--;
		y--;
		ref[i]=make_pair(x,y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	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::pair<int, int> >&)':
railway.cpp:22:6: warning: statement has no effect [-Wunused-value]
   22 |  for(i;i<ref.size();i++){
      |      ^
railway.cpp:22:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(i;i<ref.size();i++){
      |        ~^~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:101:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for(int i=0;i<r.size();i++){
      |              ~^~~~~~~~~

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