Submission #1198099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198099		Dan4Life	Railway (BOI17_railway)	C++20	7 / 100	130 ms	31796 KiB

railway

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

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;

const int mxN = (int)2e5+10;
const int INF = (int)1e9+1;
const ll LINF = (ll)2e18+1;
const int MOD = (int)1e9+7;
const int mxLg = 20;

int N, M, K;
vector<ar2> adj[mxN];



template<int SZ>
struct Fenwick{
	int fen[SZ];
	void init(){
		memset(fen,0,sizeof(fen));
	}
	void upd(int x, int v){
		for(x++; x<SZ; x+=x&-x)
			fen[x]+=v;
	}
	int sum(int x){
		int s = 0;
		for(x++; x>0; x-=x&-x)
			s+=fen[x];
		return s;
	}
};
Fenwick<mxN> fen;


int st[mxN], en[mxN];
int jmp[mxLg][mxN];
int edg[mxN];

bool isAnc(int a, int b){
	return st[a]<=st[b] and en[a]>=en[b];
}

int lca(int a, int b){
	if(isAnc(a,b)) return a;
	if(isAnc(b,a)) return b;
	for(int i = mxLg-1; i>=0; i--)
		if(jmp[i][a] and !isAnc(jmp[i][a],b))
			a = jmp[i][a];
	return jmp[0][a];
}

int dfs_tim;
int sub[mxN];

void dfs(int s, int p){
	sub[s] = 1;
	for(int j = 0; j < sz(adj[s]); j++){
		auto [u,w] = adj[s][j];
		if(u==p) continue;
		dfs(u,s); sub[s]+=sub[u];
		if(adj[s][0][0]==p or sub[adj[s][0][0]]<sub[u])
			swap(adj[s][0],adj[s][j]);
		edg[u]=w; 
	}
	en[s] = dfs_tim;
}

int head[mxN];
void dfsHld(int s, int p, int h){
	st[s] = ++dfs_tim; 
	jmp[0][s] = p; 
	head[s] = h;
	for(auto [u,w] : adj[s]){
		if(u==p) continue;
		dfsHld(u,s,adj[s][0][0]==u?h:u);
	}
	en[s] = dfs_tim;
}

void upd(int x, int y, int v){
	while(head[y]!=head[x]){
		fen.upd(st[head[y]],v);
		fen.upd(st[x]+1,-v);
		y = jmp[0][head[y]];
	}
	fen.upd(st[x],v);
	fen.upd(st[y]+1,-v);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N >> M >> K; fen.init();
	for(int i = 1; i < N; i++){
		int a, b; cin >> a >> b;
		adj[a].pb({b,i}); adj[b].pb({a,i});
	}
	dfs(1,0); dfs_tim = 0; dfsHld(1,0,1);
	for(int j = 1; j < mxLg; j++)
		for(int i = 1; i <= N; i++)
			jmp[j][i] = jmp[j-1][jmp[j-1][i]];
	
	while(M--){
		int n, x; cin >> n;
		vi v; v.clear(); for(int i =0;i<n;i++) cin >> x, v.pb(x);
		sort(all(v),[&](int a, int b){ return st[a]<st[b]; });
		for(int i = 1; i < n; i++) v.pb(lca(v[i-1],v[i]));
		sort(all(v),[&](int a, int b){ return st[a]<st[b]; });
		v.erase(unique(all(v)),end(v));
		for(int i = 1; i < sz(v); i++){
			int l = lca(v[i-1],v[i]), x = v[i];
			for(int i = mxLg-1; i>=0; i--)
				if(jmp[i][x] and !isAnc(jmp[i][x],l))
					x = jmp[i][x];
			upd(x,v[i],1);
		}
	}
	set<int> S;
	for(int i = 2; i <= N; i++)
		if(fen.sum(st[i])>=K) S.insert(edg[i]);
	cout << sz(S) << "\n";
	for(auto u : S) cout << u << " ";
	cout << "\n";
}

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