Submission #1096228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096228		win_23	Railway (BOI17_railway)	C++17	0 / 100	72 ms	35668 KiB

railway

#include <bits/stdc++.h>
using namespace std;

#define TASK "SUADUONG"
#define fi first
#define se second 
#define pb push_back
#define ll long long 
#define ii pair< int,int >
#define endl '\n'

const int INF = 1e9;
const ll LINF = 1e18;
const int N = 1e5 +5;
#define int ll

int n, m;
vector<int> adj[N + 5];
int up[N][20], h[N], f[N];
// up[u][i] là tổ tiên thứ 2^i của u 
int k;
int x[N], y[N];
namespace sub{
	void dfs(int u, int par)
	{
		for(auto v : adj[u])
		{
			if(v == par) continue;
			up[v][0] = u;

			h[v] = h[u] + 1;
			for(int i = 1; i <= 18; ++i)
			{
				up[v][i] = up[up[v][i - 1]][i - 1];
			}
			dfs(v, u);
		}
	}
	int lca(int u, int v){
		if(h[v] != h[u]) // làm cho 2 cái nút ni // ( h[u] = h[v])
		{
			if(h[u] < h[v]) swap(u , v);
			int k = h[u] - h[v]; // cần nhảy mấy bước
			for(int i = 0; (1 << i) <= k; i ++)
			{
				if(k >> i & 1)
				{
					u = up[u][i];
				}
			}
		}
		if(u == v) return u; //  khi này xét trường hợp u là tổ tiên của v
		int lg =  log2(h[u]);
		for(int i = lg ; i >= 0 ; i --)
		{
			if(up[u][0] != up[v][0])
			{
				u = up[u][i], v = up[v][i]; // timf 2 đỉnh xa nhất mà có h[u] != h[v]
			}
		}
		return up[u][0];// kq là tổ tiên của nó
	}
	void dfs2(int u, int par)
	{
		for(auto v : adj[u])
		{
			if(v == par) continue;
			dfs2(v, u);
			f[u] += f[v]; 
		}
	}
	void solve(){
		dfs(1 , 0);
		for(int i = 1; i <= m ; i++)
		{
			int u = 0, pre_u = 0, x;
			cin>>x;
			for(int i = 1; i <= x ; i++)
			{
				cin>>u;
				int cm = lca(u , pre_u);
				if(u == cm )
				{
					pre_u = u;
					f[cm] --;
					continue;
				}
				f[u] ++, f[cm]--;
				pre_u = u;
			}

		}
		dfs2(1, 0);
		set<int>v;
		for(int i = 1; i < n ; i++)
		{
			if((f[x[i]] >= k and y[i] == up[x[i]][0]) or (f[y[i]] >= k and x[i] == up[y[i]][0]) )
			{
				v.insert(i);
			}
		}
		cout<<v.size()<<endl;
		for(auto x: v) cout<<x<<' ';
	}
}
int q;
signed main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);
    //freopen(TASK".inp","r",stdin);
    //freopen(TASK".out","w",stdout);
    cin>>n>>m>>k;
    for(int i = 1; i < n ; i++)
    {
    	cin>>x[i]>>y[i];
    	adj[x[i]].pb(y[i]);
    	adj[y[i]].pb(x[i]);
    }

	sub::solve();
}

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