Submission #339272

#	Time	Username	Problem	Language	Result	Execution time	Memory
339272		Kevin_Zhang_TW	Railway (BOI17_railway)	C++17	100 / 100	261 ms	30436 KiB

railway

#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &val, T nv) {
	return val < nv ? (val = nv, true) : false;
}
template<class T>
bool chmin(T &val, T nv) {
	return nv < val ? (val = nv, true) : false;
}
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<int>> edge(n+1), req(m);
	vector<pair<int,int>> alle(n);

	for (int a, b, i = 1;i < n;++i) {
		cin >> a >> b;
		alle[i] = {a, b};
		edge[a].pb(b), edge[b].pb(a);
	}
	for (auto &vec : req) {
		int len; cin >> len;
		vec.resize(len);
		for (int &u : vec) cin >> u;
	}
	
	const int mxlg = __lg(n);

	vector<int> in(n+1), out(n+1), dfs_order;
	vector<ll> pf(n+1);
	vector<vector<int>> anc(mxlg + 1, vector<int>(n+1));

	dfs_order.reserve(n);

	function<void(int,int)> dfs = [&](int x, int lst) {
		static int t;
		in[x] = ++t;
		anc[0][x] = lst;
		for (int u : edge[x]) if (u != lst)
			dfs(u, x);
		out[x] = ++t;
		dfs_order.pb(x);
	};

	dfs(1, 1);
	
	for (int d = 1;d <= mxlg;++d) 
		for (int i = 1;i <= n;++i)
			anc[d][i] = anc[d-1][ anc[d-1][i] ];

	auto isanc = [&](int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; };
	auto getlca = [&](int a, int b) {
		for (int d = mxlg;d >= 0;--d)
			if (!isanc(anc[d][a], b))
				a = anc[d][a];
		return isanc(a, b) ? a : anc[0][a];
	};

	//for (int i = 1;i <= n;++i) DE(i, in[i], out[i]);

	vector<ll> bitval(n*2+1);
	vector<pair<int,ll>> allop;
	auto add = [&](int i, ll v) {
		allop.pb(i, v);
		for (;i <= n*2;i += i&-i) bitval[i] += v;
	};
	auto reset = [&]() {
		for (auto [i, v] : allop) add(i, -v);
		allop.clear();
	};
	auto qry = [&](int i) { 
		ll res = 0;
		for (;i;i ^= i&-i) res += bitval[i];
		return res;
	};
	auto cmp1 = [&](int x, int y) {
		return in[x] < in[y];
	};
	auto cmp2 = [&](int x, int y) {
		return out[x] < out[y];
	};

	for (auto &vec : req) {

		sort(AI(vec), cmp1);
		for (int u : vec)
			add(in[u], 1), ++pf[u];

		vector<int> par;

//		for (int i = 0;i < vec.size();++i) for (int j = i+1;j < vec.size();++j)
//			par.pb(getlca(vec[i], vec[j]));
//
		for (int i = 1;i < vec.size();++i)
			par.pb(getlca(vec[i-1], vec[i]));

		sort(AI(par), cmp2);
		par.resize(unique(AI(par)) - begin(par));

		debug(AI(par));

		for (int u : par) {
			int dn = qry(out[u]) - qry(in[u]-1), to_add = (u != par.back()) - dn;
			//DE(u, dn, to_add);
			pf[u] += to_add;
			add(in[u], to_add);
		}

		//for (int i = 1;i <= n;++i) DE(i, qry(out[i]) - qry(in[i]-1));

		reset();
		//break;
	}

	for (int u : dfs_order) if (u != 1) pf[ anc[0][u] ] += pf[u];

	for (int i = 1;i <= n;++i) DE(i, pf[i]);

	vector<int> res;

	for (int i = 1;i < n;++i) {
		auto &[a, b] = alle[i];
		// I want a is up
		if (in[a] > in[b]) swap(a, b);
		if (pf[b] >= k) res.pb(i);
	}
	
	cout << res.size() << '\n';
	for (int u : res) cout << u << " \n"[u == res.back()];
}

Compilation message (stderr)

railway.cpp: In function 'int32_t main()':
railway.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for (int i = 1;i < vec.size();++i)
      |                  ~~^~~~~~~~~~~~
railway.cpp:21:20: warning: statement has no effect [-Wunused-value]
   21 | #define debug(...) 0
      |                    ^
railway.cpp:120:3: note: in expansion of macro 'debug'
  120 |   debug(AI(par));
      |   ^~~~~
railway.cpp:20:17: warning: statement has no effect [-Wunused-value]
   20 | #define DE(...) 0
      |                 ^
railway.cpp:137:29: note: in expansion of macro 'DE'
  137 |  for (int i = 1;i <= n;++i) DE(i, pf[i]);
      |                             ^~

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