Submission #513432

#	Time	Username	Problem	Language	Result	Execution time	Memory
513432		Aditya_A_garwal	Railway (BOI17_railway)	C++17	100 / 100	105 ms	24124 KiB

railway

// Krishnaya vaasudevaya
// Devaki nandanayacha
// Nanda gopakumaraya
// Govindaya namoh namaha
// Jay ganeshji, Jay Guruji, Jay Ram-bhakt Hanumanji

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define ff first
#define ss second

#define pb emplace_back
#define eb emplace

// Competion only
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;

const int inf = 1e9 + 7;
const ll llinf = 1e18 + 7;

constexpr ll mod = 1e9 + 7;

const vector<pii> dirs4 = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
const vector<pii> dirs8 = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll fastPow(ll a, ll b)
{
	ll res = 1;
	while(b) {
		if(b & 1)
			res *= a;
		a *= a, b >>= 1;
	}
	return res;
}

ll fastPow(ll a, ll b, ll m)
{
	ll res = 1;
	a %= m;
	while(b) {
		if(b & 1)
			(res *= a) %= m;
		(a *= a) %= m, b >>= 1;
	}
	return res;
}

ll modinv(ll x, ll m)
{
	return fastPow(x, m - 2, m);
}

ll moddiv(ll numerator, ll denominator, ll m) {
	return numerator * modinv(denominator, m);
}

template<typename T>
inline void maximize(T &trg, T src) {
	trg = max(trg, src);
}

template<typename T>
inline void minimize(T &trg, T src) {
	trg = min(trg, src);
}

template<typename T>
constexpr ostream &operator<<(ostream &stream, const vector<T> &other) {
	stream << '[';
	size_t n = other.size();

	if(n > 0) {
		for(size_t i = 0; i < n - 1; i++)
			stream << other[i] << ", ";
		stream << other[n - 1];
	}

	return stream << ']';
}

template<typename T>
constexpr ostream &operator<<(ostream &stream, const set<T> &other) {
	stream << '{';

	size_t n = other.size();

	if(n > 0) {
		auto it = other.begin();
		for(size_t i = 0; i < n-1; i++)
			stream << *it << ", ", ++it;
		stream << *it;
	}

	return stream << '}';
}

template<typename T>
constexpr ostream &operator<<(ostream &stream, const multiset<T> &other) {
	stream << '{';

	size_t n = other.size();

	if(n > 0) {
		auto it = other.begin();
		for(size_t i = 0; i < n-1; i++)
			stream << *it << ", ", ++it;
		stream << *it;
	}

	return stream << '}';
}

template<typename T>
constexpr ostream &operator<<(ostream &stream, const ordered_set<T> &other) {
	stream << '{';

	size_t n = other.size();

	if(n > 0) {
		auto it = other.begin();
		for(size_t i = 0; i < n-1; i++)
			stream << *it << ", ", ++it;
		stream << *it;
	}

	return stream << '}';
}

template<typename T1, typename T2>
constexpr ostream &operator<<(ostream &stream, const map<T1, T2> &other) {
	stream << '{';

	size_t n = other.size();

	if(n > 0) {
		auto it = other.begin();
		for(size_t i = 0; i < n-1; i++)
			stream << (*it).first << ':' << (*it).second << ", ", ++it;
		stream << (*it).first << ':' << (*it).second;
	}

	return stream << '}';
}

template<typename T1, typename T2>
constexpr ostream &operator<<(ostream &stream, const multimap<T1, T2> &other) {
	stream << '{';

	size_t n = other.size();

	if(n > 0) {
		auto it = other.begin();
		for(size_t i = 0; i < n-1; i++)
			stream << (*it).first << ':' << (*it).second << ", ", ++it;
		stream << (*it).first << ':' << (*it).second;
	}

	return stream << '}';
}

template<typename T1, typename T2>
constexpr ostream &operator<<(ostream &stream, const unordered_map<T1, T2> &other) {
	stream << '{';

	size_t n = other.size();

	if(n > 0) {
		auto it = other.begin();
		for(size_t i = 0; i < n-1; i++)
			stream << (*it).first << ':' << (*it).second << ", ", ++it;
		stream << (*it).first << ':' << (*it).second;
	}

	return stream << '}';
}

template<typename T1, typename T2>
constexpr ostream &operator<<(ostream &stream, const pair<T1, T2> &other) {
	return stream << '(' << other.first << ", " << other.second << ')';
}

template<typename T>
istream &operator>>(istream &stream, vector<T> &other) {
	for(auto &e : other)
		stream >> e;

	return stream;
}

template<typename T1, typename T2>
istream &operator>>(istream &stream, pair<T1, T2> &other) {
	stream >> other.first >> other.second;
	return stream;
}

template<size_t I = 0, typename ...T>
ostream &operator<<(ostream &stream, const tuple<T...> &other) {

	if constexpr(I == 0)
		stream << '(';

	stream << get<I>(other);

	if constexpr(I < sizeof...(T) - 1) {
		stream << ", ";
		return operator<<<I + 1>(stream, other);
	}
	return stream << ')';
}

constexpr int mxn = 100'010;
constexpr int mxlog = 20;

int n, q, k;

int timer = 0;

vii adj[mxn];
int pre[mxn][mxlog];

int dep[mxn]{};

int tin[mxn];
int qry[mxn];

int freq[mxn]{};
vi res;

bool comp(const int &a, const int &b) {
	return tin[a] < tin[b];
}

void dfs1(int cur, int prv) {

	tin[cur] = timer++;

	pre[cur][0] = prv;
	for(int i = 1; i < mxlog; i++)
		pre[cur][i] = pre[pre[cur][i - 1]][i - 1];

	for(auto &[nxt, i]: adj[cur]) {
		if(nxt == prv)
			continue;
		dep[nxt] = 1 + dep[cur];
		dfs1(nxt, cur);
	}
}

void dfs2(int cur, int prv) {

	for(auto &[nxt, i] : adj[cur]) {
		if(nxt == prv)
			continue;

		dfs2(nxt, cur);
		freq[cur] += freq[nxt];

		freq[nxt] /= 2;
		if(freq[nxt] >= k)
			res.pb(i);
	}

	assert(freq[cur] % 2 == 0);
}

int ances(int u, int d) {

	for(int i = mxlog - 1; i >= 0; i--) {
		if(d & (1 << i))
			u = pre[u][i];
	}

	return u;
}

int LCA(int u, int v) {

	if(dep[u] > dep[v])
		swap(u, v);

	v = ances(v, dep[v] - dep[u]);

	if(u == v)
		return u;

	for(int i = mxlog - 1; i >= 0; i--) {
		if(pre[u][i] != pre[v][i]) {
			u = pre[u][i];
			v = pre[v][i];
		}
	}

	assert(pre[u][0] == pre[v][0]);
	return pre[u][0];
}

void query() {

	int m; cin >> m;

	for(int i = 0; i < m; i++) {
		cin >> qry[i], --qry[i];
	}

	sort(qry, qry + m, comp);
	qry[m] = qry[0];

	for(int i = 0; i < m; i++) {

		int &u = qry[i];
		int &v = qry[i + 1];
		int mid = LCA(u, v);

		++freq[u];
		++freq[v];
		freq[mid] -= 2;
	}
}

inline void solve() {

	cin >> n >> q >> k;

	for(int i = 1, u, v; i < n; i++) {

		cin >> u >> v, --u, --v;

		if(u > v)
			swap(u, v);

		adj[u].pb(v, i);
		adj[v].pb(u, i);

		// idx[{u, v}] = i;
	}

	dfs1(0, 0);

	while(q--)
		query();

	dfs2(0, 0);

	sort(res.begin(), res.end());

	cout << res.size() << '\n';
	for(auto &e : res)
		cout << e << ' ';
	cout << '\n';
}

int main(int argc, char *argv[]) {
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt",  "w", stdout);
// #endif

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	solve();

	return 0;
}

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