Submission #968036

#	Time	Username	Problem	Language	Result	Execution time	Memory
968036		NintsiChkhaidze	Railway (BOI17_railway)	C++17	100 / 100	223 ms	37528 KiB

railway

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define int ll
using namespace std;

const int N = 1e5 + 5;
vector <int> v[N];
int timer,tin[N],tout[N],dep[N],d[25][N];
pii a[N];
int fen[N],p[N];

void dfs(int x,int par){
	tin[x] = ++timer;
	d[0][x] = par;
	dep[x] = dep[par] + 1;
	for (int to: v[x])
		if (to != par) dfs(to,x);
	tout[x] = timer;
}

void upd(int idx,int dl){
	while (idx <= 100000){
		fen[idx]+=dl;
		idx+=(idx&(-idx));
	}
}
int get(int idx){
	int s = 0;
	while (idx > 0){
		s += fen[idx];
		idx -= (idx & (-idx));
	}
	return s;
}

int lca(int x,int y){
	if (dep[x] < dep[y]) swap(x,y);
	for (int i = 18; i >= 0; i--)
		if (dep[d[i][x]] >= dep[y]) x = d[i][x];

	if (x == y) return x;
	for (int i = 18; i >= 0; i--)
		if (d[i][x] != d[i][y]) x = d[i][x],y = d[i][y];

	return d[0][x];
}

void updatepath(int x,int y){
	upd(tin[x],+1);
	upd(tin[y],+1);
	upd(tin[lca(x,y)],-2);
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n,m,k;
	cin>>n>>m>>k;

	vector <pii> edges;
	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
		edges.pb({a,b});
	}

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

	for (int i=0;i<edges.size();i++){
		int x = edges[i].f,y = edges[i].s;
		if (dep[x] < dep[y]) swap(x,y);
		p[x] = i + 1;
	}

	for (int i = 1; i <= m; i++){
		int t;
		cin>>t;

		for (int j = 1; j <= t; j++){
			cin >> a[j].s;
			a[j].f = tin[a[j].s];
		}

		sort(a+1,a+t+1);
		for (int j = 2; j <= t; j++)
			updatepath(a[j-1].s,a[j].s);
		updatepath(a[t].s,a[1].s);
	}

	vector <int> ans;
	for (int i = 2; i <= n; i++){
		if (get(tout[i]) - get(tin[i] - 1) >= 2*k) ans.pb(p[i]);
	}
	cout<<ans.size()<<endl;
	sort(ans.begin(),ans.end());
	for (int x: ans)
		cout<<x<<" ";
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:78:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i=0;i<edges.size();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