Submission #378354

#	Time	Username	Problem	Language	Result	Execution time	Memory
378354		soroush	Railway (BOI17_railway)	C++17	100 / 100	189 ms	20536 KiB

railway

/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 100;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , m , k;
vector < pair < pii , int > > e;
vector < int > adj[maxn];
vector < int > ans;
int head[maxn] , par[maxn] , h[maxn] , sz[maxn] , mx[maxn] , st[maxn] , ft[maxn] , ti = 0;

void szdfs(int v){
	sz[v] = 1;
	for(auto u : adj[v])if(u ^ par[v]){
		par[u] = v , h[u] = h[v] + 1 , szdfs(u) , sz[v] += sz[u];
		if(sz[u] > sz[mx[v]])mx[v] = u;
	}
}

void hldfs(int v){
	st[v] = ++ti;
	if(mx[v])head[mx[v]] = head[v] , hldfs(mx[v]);
	for(auto u : adj[v])if(u^par[v] and u^mx[v])
		head[u] = u , hldfs(u);
	ft[v] = ti;
}

int lca(int u , int v){
	while(head[u] ^ head[v]){
		if(h[head[u]] < h[head[v]])swap(u , v);
		u = par[head[u]];
	}
	return((h[u] < h[v]) ? u : v);
}

int fen[maxn];
void add(int pos , int x){
	for(; pos < maxn ; pos += pos & -pos)
		fen[pos] += x;
}

void add(int l , int r , int x){
	add(l , x);
	add(r + 1 , -x);
}

int get(int pos){
	int res = 0;
	for(; pos ; pos -= pos & -pos)
		res += fen[pos];
	return(res);
}

void addpath(int v , int anc){
	while(head[v] ^ head[anc]){
		add(st[head[v]] , st[v] , 1);
		v = par[head[v]];
	}
	add(st[anc] , st[v] , 1);
	add(st[anc] , st[anc] , -1);
}

void Add(int u , int v){
	int lc = lca(u , v);
	addpath(u , lc);
	addpath(v , lc);
}

int32_t main(){
	migmig;
	cin >> n >> m >> k;
	for(int i = 1 ; i < n ; i ++){
		int u , v; 
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
		e.pb({{u , v} , i});
	}
	h[1] = 1;
	szdfs(1);
	hldfs(1);
	while(m --){
		int k;
		cin >> k;
		vector < int > vec(k);
		for(int i = 0 ; i < k ; i ++)
			cin >> vec[i];
		sort(vec.begin() , vec.end() , [](int i , int j){return st[i] < st[j];});
		vec.pb(vec[0]);
		for(int i = 0 ; i < k ; i ++)
			Add(vec[i] , vec[i + 1]);
	}
	for(auto x : e){
		int v = x.first.first;
		int u = x.first.second;
		int i = x.second;
		if(par[u] ^ v)swap(u , v);
		if(get(st[u]) >= 2 * k)ans.pb(i);
	}
	cout << ans.size() << endl;
	for(auto e : ans)
		cout << e << ' ';
	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