Submission #419719

#	Time	Username	Problem	Language	Result	Execution time	Memory
419719		victoriad	Railway (BOI17_railway)	C++14	23 / 100	1090 ms	20184 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(a>b)swap(a,b);
	for(int i=0;i<ref[a].size();i++){
		if(ref[a][i].first==b)
		return ref[a][i].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);
	}
	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:15: 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(int i=0;i<ref[a].size();i++){
      |              ~^~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:102:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  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:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^

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