Submission #501317

#	Time	Username	Problem	Language	Result	Execution time	Memory
501317		Arnch	Railway (BOI17_railway)	C++17	7 / 100	98 ms	51268 KiB

railway

// oooo
/*
 be hengam shena mesle y dasto pa cholofti ~
 bepa to masire dahane koose neyofti ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long long ld;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

const ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969, Log = 30;

int h[N];
int st[N];
ll cnt[N];
int u[N], v[N];
int par[N][Log];

int t;

bool mark[N];

vector<ll> vc, ans, G[N];

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

void dfs(int x, int p) {
	mark[x] = 1, par[x][0] = p, st[x] = t++;

	for(int i = 1; i < Log; i++)
		par[x][i] = par[par[x][i - 1]][i - 1];

	for(auto i : G[x]) {
		if(mark[i]) continue;
		
		h[i] = h[x] + 1;
		dfs(i, x);
	}
}

int get_par(int x, int y) {
	for(int i = 0; i < Log; i++)
		if((y >> i) & 1) 
			x = par[x][i];

	return x;
}

int lca(int x, int y) {
	if(h[x] > h[y]) swap(x, y);
	
	y = get_par(y, h[y] - h[x]);


	if(x == y) return x;

	for(int i = Log - 1; i >= 0; i--) {
		if(par[x][i] != par[y][i]) 
			x = par[x][i], y = par[y][i];
	}

	return par[x][0];
}

void main_dfs(int x, int p) {
	mark[x] = 1;
	for(auto i : G[x]) {
		if(mark[i]) continue;

		main_dfs(i, x);
		cnt[x] += cnt[i];
	}
}


int main() {
    fast_io;
	
	int n, m, k;
	cin >>n >>m >>k;

	for(int i = 0; i < n - 1; i++) {
		cin >>u[i] >>v[i];
		G[u[i]].push_back(v[i]), G[v[i]].push_back(u[i]);
	}

	dfs(1, 0);

	for(int i = 0; i < m; i++) {
		int s; cin >>s;
		vc.clear();
		for(int j = 0; j < s; j++) {
			int x; cin >>x;
			vc.push_back(x);
		}
		if(s == 1) continue;

		sort(all(vc), cmp);
		for(int i = 1; i < Sz(vc); i++) {
			int lc = lca(vc[i], vc[i - 1]);
//			cout<<"^&" <<vc[i - 1] <<" " <<vc[i] <<" " <<lc <<endl;
			cnt[lc]--;
			cnt[vc[i - 1]]++, cnt[vc[i]]++;
			if(lc == vc[i]) cnt[vc[i]]--;
			else if(lc == vc[i - 1]) cnt[vc[i - 1]]--;
		}
		int lc = lca(vc[0], vc.back());
		cnt[lc]--;
		cnt[vc[0]]++, cnt[vc.back()]++;
		if(lc == vc[0]) cnt[vc[0]]--;
		else if(lc == vc.back()) cnt[vc.back()]--;
	}

	memset(mark, 0, sizeof(mark));
	
	main_dfs(1, 0);

	for(int i = 1; i <= n; i++) {
		cnt[i] /= 2;
	}

	for(int i = 0; i < n - 1; i++) {
		if(h[u[i]] > h[v[i]]) swap(u[i], v[i]);
		if(cnt[v[i]] >= k) ans.push_back(i + 1);
	}

	sort(all(ans));

	cout<<Sz(ans) <<"\n";
	for(auto i : ans) cout<<i <<" ";
			

	return 0;
}

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