Submission #1036710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036710		pacman	Railway (BOI17_railway)	C++17	0 / 100	114 ms	72836 KiB

railway

/******************************************************
| '_ \ / _` |/ __| '_ ` _ \ / _` | '_ \
| |_) | (_| | (__| | | | | | (_| | | | |
| .__/ \__,_|\___|_| |_| |_|\__,_|_| |_|
|_|

__|      |____________________________________________
     ,--.    ,--.          ,--.   ,--.
    |oo  | _  \  `.       | oo | |  oo|
o  o|~~  |(_) /   ;       | ~~ | |  ~~|o  o  o  o  o
    |/\/\|   '._,'        |/\/\| |/\/\|
__________________        ____________________________
******************************************************/

#include <bits/stdc++.h>
//#include "bigint.h"
#define db(x) cerr << #x << ": " << x << endl
#define print cerr << "Ah shit, here we go agian" << endl
#define ll long long int
#define vii vector<int>
#define pii pair<int ,int>
#define vpi vector< pii >
#define ff first
#define ss second
#define mp make_pair
#define mod 1000000007

using namespace std;

const int maxn = 1e5 + 100, lg = 30;

int n ,m ,k, godfather;

vii adj[maxn];
int par[lg][maxn], h[maxn];
map<int ,int> mapi;
map<pii, bool> e;
vii ver;
map<int, pii> edge;

void dfs(int v, int mpar){
	par[0][v] = mpar;
	
	for(int i = 1 ; i < lg; i++){
		par[i][v] = par[i - 1][par[i - 1][v]];
	}
	
	for(auto u : adj[v]){
		if(u != mpar){
			h[u] = h[v] + 1;
			dfs(u ,v);
		}
	}
}

int lca (int u, int v){
	if (h[u] < h[v])
		swap(u, v);
			
	for(int i = lg - 1; i >= 0 ;i--){
		if(h[par[i][u]] >= h[v]){
			u = par[i][u];
		}
	}
	if (u == v)
		return u;
		
	for(int i = lg - 1; i >= 0 ;i--){
		if(par[i][u] != par[i][v]){
			u = par[i][u] , v= par[i][v];
		}
	}
	return par[0][u];
}


void find_par(int v){
	if(v == godfather){
		return;
	}
	e[{v ,par[0][v]}] = true;
	e[{par[0][v], v}] = true;
	find_par(par[0][v]);
}


void solve(){
	cin >> n >> m >> k;
	
	for(int i = 0 ;i < n - 1; i++){
		int x ,y;
		cin >> x >> y;
		
		adj[x].push_back(y);
		adj[y].push_back(x);
		edge[i] = {x ,y};
	}
	for(int i = 0 ; i < m; i++){
		int x;
		cin >> x;
		while(x--){
			int a;
			cin >> a;
			mapi[a]++;
		}
	}
	
	for(int i = 1 ; i <= n; i++){
		if(mapi[i] >= k){
			ver.push_back(i);
		}
	}
	
	h[1] = 1;
	dfs(1 ,0);
	
	godfather = lca(ver[0], ver[1]);
	for(int i = 2; i < ver.size(); i++){
		godfather = lca(godfather, ver[i]);
	}
	
	for(int i = 0 ;i < ver.size(); i++){
		find_par(ver[i]);
	}
	
	int cnt= 0;

	cout << ver.size() << endl;
	for(int i = 0 ;i < n; i++){
		if(e[edge[i]] == true){
			cout << edge[i].ff << ' ' << edge[i].ss << endl;
		}
	}
}


signed main(){

	ios_base::sync_with_stdio(0), cin.tie(0) ,cout.tie(0);

	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}

	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void solve()':
railway.cpp:118:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for(int i = 2; i < ver.size(); i++){
      |                 ~~^~~~~~~~~~~~
railway.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |  for(int i = 0 ;i < ver.size(); i++){
      |                 ~~^~~~~~~~~~~~
railway.cpp:126:6: warning: unused variable 'cnt' [-Wunused-variable]
  126 |  int cnt= 0;
      |      ^~~

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