Submission #419655

#	Time	Username	Problem	Language	Result	Execution time	Memory
419655		victoriad	Railway (BOI17_railway)	C++14	0 / 100	256 ms	524292 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);
	}
}

void conectar(int a,int b,vector<int>&d,vector<int>&p,vector<int>&con,int k,vector<int>&r,vector<vector<int> >&id){
	if(d[a]<d[b])swap(a,b);
	int dif=d[a]-d[b];
	while(d[a]!=d[b]){
		int pa=p[a];
		con[id[a][pa]]++;
		if(con[id[a][pa]]==k && pa!=a){
			r.push_back(id[a][pa]);
		}
		a=pa;
	}
	while(a!=b){
		int pa=p[a];
		int pb=p[b];
		con[id[a][pa]]++;
		con[id[b][pb]]++;
		if(con[id[a][pa]]==k && pa!=a){
			r.push_back(id[a][pa]);
		}
		if(con[id[b][pb]]==k && pb!=b){
			r.push_back(id[b][pb]);
		}
		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<int> >ref(n+1);
	vector<int>re(n+1,0);
	for(int i=0;i<n+1;i++)ref[i]=re;
	vector<vector<int> >a(n);
	for(int i=0;i<n-1;i++){
		cin>>x>>y;
		x--;
		y--;
		ref[x][y]=i+1;
		ref[y][x]=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;
		for(int o=0;o<j/2;o++){
			cin>>x>>y;
			x--;
			y--;
			conectar(x,y,depth,parent,con,k,r,ref);
		}
	}
	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 'void conectar(int, int, std::vector<int>&, std::vector<int>&, std::vector<int>&, int, std::vector<int>&, std::vector<std::vector<int> >&)':
railway.cpp:22:6: warning: unused variable 'dif' [-Wunused-variable]
   22 |  int dif=d[a]-d[b];
      |      ^~~
railway.cpp: In function 'int main()':
railway.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  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