Submission #1040245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040245		soroostab	Railway (BOI17_railway)	C++14	100 / 100	67 ms	32200 KiB

railway

#include <bits/stdc++.h>
#define ll long long int
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pcc pair<char,char>
#define pbb pair<bool,bool>
#define PB push_back
#define PF push_front
#define MOD 1000000007
#define intxt freopen("input.txt","r",stdin)
#define outtxt freopen("output.txt","w",stdout)

using namespace std;

const int MAXN = 1e5 + 10;
ll n ,q ,k ,q1 ,q2 ,qq ,x = 1;
ll par[MAXN][20] ,h[MAXN] ,st[MAXN];
ll change[MAXN] ,ans[MAXN];
vector <pii> adj[MAXN];
vector <int> isvalid;

inline void dfs(int v , int p = 0) {
	st[v] = x;
	x++;
	for(auto u : adj[v]) {
		if(u.f == p) {
			continue;
		}
		h[u.f] = h[v] + 1;
		par[u.f][0] = v;
		dfs(u.f , v);
	}
}

inline ll bridge_cost(int v , int p = 0) {
	int cnt = change[v];
	for(auto u : adj[v]) {
		if(u.f == p) {
			continue;
		}
		ans[u.s] = bridge_cost(u.f ,v);
		cnt += ans[u.s];
		if(ans[u.s] >= (2 * k)) {
			isvalid.PB(u.s);
		}
	}
	return cnt;
}

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

bool cmp(const int u , const int v) {
	return st[v] < st[u];
}

int main() {

	ios_base::sync_with_stdio(0);
	
	cin >> n >> q >> k;
	
	for(int i = 1 ; i < n ; i++) {
		cin >> q1 >> q2;
		adj[q1].PB(make_pair(q2 , i));
		adj[q2].PB(make_pair(q1 , i));
	}
	
	dfs(1);
	
	for(int j = 1 ; j <= 17 ; j++) {
		for(int i = 1 ; i <= n ; i++) {
			par[i][j] = par[par[i][j - 1]][j - 1];
		}
	}
	
	while(q--) {
		
		cin >> qq;
		
		int a[qq + 10];
		for(int i = 1 ; i <= qq ; i++) {
			cin >> a[i];
		}
		sort(a + 1 ,a + qq + 1 ,cmp);
		
		for(int i = 1 ; i < qq ; i++) {
			change[LCA(a[i] ,a[i + 1])] -= 2;
			change[a[i]]++;
			change[a[i + 1]]++;
		}
		change[LCA(a[qq] ,a[1])] -= 2;
		change[a[qq]]++;
		change[a[1]]++;
		
	}
	
	bridge_cost(1);
	
	sort(isvalid.begin() ,isvalid.end());
	cout << isvalid.size() << endl;
	for(auto x : isvalid) {
		cout << x << " ";
	}
	
}
// Hello

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