Submission #983014

#	Time	Username	Problem	Language	Result	Execution time	Memory
983014		Acanikolic	Railway (BOI17_railway)	C++14	23 / 100	1057 ms	32612 KiB

railway

#include <bits/stdc++.h>

//#define int long long

#define pb push_back

#define F first

#define S second

const int N = 1e5 + 10;

const int inf = 2e9;

const int mod = 998244353;

const int lg = 17;

using namespace std;

int up[N][lg],in[N],out[N],timer = 0,pr[N],ans[N];
vector<int>g[N];

bool inn(int u,int v) {
	//dal je v u u
	if(in[u] <= in[v] && out[u] >= out[v]) return true;
	return false;
}

int lca(int u,int v) {
	if(inn(u,v)) return u;
	if(inn(v,u)) return v;
	for(int j = lg - 1; j >= 0; j--) {
		if(up[u][j] == 0) continue;
		if(!inn(up[u][j],v)) u = up[u][j];
	}
	return up[u][0];
}

void dfs(int x,int par) {
	pr[x] = par;
	up[x][0] = par;
	in[x] = ++timer;
	for(auto X : g[x]) {
		if(X != par) {
			dfs(X,x);
		}
	}
	out[x] = timer;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	int n,m,k;
	cin >> n >> m >> k;
	map<pair<int,int>,int>index;
	for(int i = 1; i <= n - 1; i++) {
		int u,v;
		cin >> u >> v;
		index[{u,v}] = i;
		index[{v,u}] = i;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1,0);
	for(int j = 1; j < lg; j++) {
		for(int i = 1; i <= n; i++) {
			up[i][j] = up[up[i][j - 1]][j - 1];
		}
	}
	for(int i = 1; i <= m; i++) {
		int s;
		cin >> s;
		vector<int>b(s + 1);
		for(int j = 1; j <= s; j++) cin >> b[j];
		int LCA = lca(b[1],b[2]);
		for(int j = 3; j <= s; j++) LCA = lca(LCA,b[j]);
		bool was[n + 1];
		for(int j = 1; j <= n; j++) was[j] = false;
		for(int j = 1; j <= s; j++) {
			while(b[j] != LCA) {
				was[b[j]] = true;
				b[j] = pr[b[j]];
 			}
		}
		for(int j = 1; j <= n; j++) {
			if(was[j]) {
				ans[index[{pr[j],j}]] += 1;
			}
		}
	}
	vector<int>rez;
	for(int i = 1; i <= n - 1; i++) if(ans[i] >= k) rez.pb(i);
	cout << rez.size() << "\n";
	for(auto X : rez) cout << X << " ";
    return 0;
}

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