Submission #1096422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096422		Nguyen22cpp	Railway (BOI17_railway)	C++14	7 / 100	114 ms	28108 KiB

railway

// author : Nguyễn Trọng Nguyễn - ITK22 NBK
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair <int, int>
#define fi first
#define sc second

const int maxn = (int)1e5;
const int inf = (int)1e9;
const int LG = 16;

int n, m, k;
vector <int> adj[maxn + 5];
ii edge[maxn + 5];

int timer = 0;
int up[LG + 5][maxn + 5], tin[maxn + 5], tout[maxn + 5];

int sz[maxn + 5], npos = 0, nchain = 0;
int apos[maxn + 5], chains[maxn + 5], head[maxn + 5];

int st[maxn * 4 + 5], lazy[maxn * 4 + 5], cnt[maxn + 5];

void dfs (int u = 1, int p = 1) {
	tin[u] = ++timer;
	
	sz[u] = 1;
	up[0][u] = p;

	for (int e = 1; e <= LG; e++)
		up[e][u] = up[e - 1][up[e - 1][u]];

	for (auto v : adj[u]) {
		if (v == p) continue;
		dfs(v, u);
		sz[u] += sz[v];
	}

	tout[u] = timer;
}

bool isAncestor (int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca (int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;

    for (int exp = LG; exp >= 0; exp--)
        if (!isAncestor(up[exp][u], v)) 
            u = up[exp][u];
        
    return up[0][u];
}

void hld (int u = 1, int p = 1) {
	if (head[nchain] == 0) head[nchain] = u;
	chains[u] = nchain;
	apos[u] = ++npos;

	int hv = -1;
	for (auto v : adj[u]) {
		if (v == p) continue;
		if (hv == -1 or sz[hv] < sz[v]) 
			hv = v;
	}

	if (hv != -1) hld(hv, u);

	for (int v : adj[u]) {
		if (v == p or v == hv) continue;
		nchain++;
		hld(v, u);
	}
}

void down (int id, int l, int mid, int r) {
	if (lazy[id] == 0) return ;

	int &v = lazy[id];

	st[id << 1] += (mid - l + 1) * v;
	st[id << 1 | 1] += (r - mid) * v;

	lazy[id << 1] += v;
	lazy[id << 1 | 1] += v;

	v = 0;
}

void update (int id, int l, int r, int u, int v, int val) {
	if (v < l or r < u) return ;
	if (u <= l and r <= v) {
		st[id] += (r - l + 1) * val;
		lazy[id] += val;
		return ;
	}

	int mid = l + r >> 1;
	down(id, l, mid, r);

	update(id << 1, l, mid, u, v, val);
	update(id << 1 | 1, mid + 1, r, u, v, val);

	st[id] = st[id << 1] + st[id << 1 | 1];
}

int get (int id, int l, int r, int u) {
	if (u < l or r < u) return 0;
	if (l == r) return st[id];

	int mid = l + r >> 1;
	down(id, l, mid, r);

	return get(id << 1, l, mid, u) + get(id << 1 | 1, mid + 1, r, u);
}

void QUERY_UPDATE (int u, int _lca, int val) {
	while (true) {
		if (chains[u] == chains[_lca]) {
			update(1, 1, n, apos[_lca], apos[u], val);
			return ;
		}

		update(1, 1, n, apos[head[chains[u]]], apos[u], val);
		u = up[0][head[chains[u]]];
	}
}

int QUERY_GET (int u) {
	return get(1, 1, n, u);
}

void init () {
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edge[i] = {u, v};
	}
}

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

void process () {
	dfs();
	hld();

	while (m--) {
		vector <int> fix;

		int x; cin >> x;
		while (x--) {
			int u; cin >> u;
			fix.push_back(u);
		}

		sort(fix.begin(), fix.end(), cmp);

		int cur = fix[0];
		for (auto v : fix) {
			int _lca = lca(v, cur);
			QUERY_UPDATE(v, _lca, 1);
			QUERY_UPDATE(_lca, _lca, -1);
			cur = v;
		}
	}

	vector <int> node;
	for (int i = 1; i < n; i++) {
		int u, v; tie(u, v) = edge[i];
		int ans = up[0][u] == v ? QUERY_GET(u) : QUERY_GET(v);
		if (ans >= k) node.push_back(i);
	}

	cout << (int)node.size() << '\n';
	for (int v : node) cout << v << ' ';
}

signed main () {
	cin.tie(0)->sync_with_stdio(false);

	init();
	process();

	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void update(int, int, int, int, int, int)':
railway.cpp:102:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |  int mid = l + r >> 1;
      |            ~~^~~
railway.cpp: In function 'int get(int, int, int, int)':
railway.cpp:115:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |  int mid = l + r >> 1;
      |            ~~^~~

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