Submission #915115

#	Time	Username	Problem	Language	Result	Execution time	Memory
915115		penguin133	Railway (BOI17_railway)	C++17	100 / 100	215 ms	68552 KiB

railway

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second

int sz[1000005], head[1000005], par[1000005], dep[1000005], S[1000005];
int up[1000005];
vector<int>v[1000005];
int n, q;
vector<pii>adj;

int getr(int x){
	return (par[x] == x ? x : par[x] = getr(par[x]));
}

void merge(int a, int b){
	a = getr(a), b = getr(b);
	if(a != b)par[b] = a;
}

void dfs(int x, int p, int d){
	dep[x] = d;
	up[x] = p;
	sz[x] = 1;
	for(auto i : v[x]){
		if(i == p)continue;
		dfs(i, x, d + 1);
		sz[x] += sz[i];
	}
}


struct node{
	int s,e,m,val, lazy = 0;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)>>1;
		val = 0;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
	}
	void propo(){
		if(lazy){
			val += lazy * (e - s + 1);
			if(s != e)l->lazy += lazy, r->lazy += lazy;
			lazy = 0;
		}
	}
	void upd(int a, int b, int c){
		//cerr << "UPD " << a << " " << b << " " << c << '\n';
		if(a == s && b == e)lazy += c;
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->propo(), r->propo();
			val = l->val + r->val;
		}
	}
	int query(int a, int b){
		propo();
		if(a == s && b == e)return val;
		else if( b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return (l->query(a, m) + r->query(m+1, b));
	}
}*root;
int cnt = 1;
void dfs2(int x, int h, int par){
	S[x] = cnt++;
	head[x] = h;
	int maxi = 0, in = -1;
	for(auto i : v[x]){
		if(i == par)continue;
		if(maxi < sz[i])maxi = sz[i], in = i;
	}
	for(auto i : v[x]){
		if(i == par)continue;
		if(i == in)dfs2(i, h, x);
	}
	for(auto i : v[x]){
		if(i != par && i != in)dfs2(i, i, x);
	}
}
vector <pi> upds;
void chng(int a, int b) {
    for (; head[a] != head[b]; b = up[head[b]]) {
		//cerr << a << " " << b << " " << head[a] << " " << head[b] << '\n';
        if (dep[head[a]] > dep[head[b]])
            swap(a, b);
        //root->upd(S[head[b]], S[b], 1);
        upds.push_back({S[head[b]], S[b]});
    }
    if (dep[a] > dep[b])
        swap(a, b);
    if(S[a] != S[b])upds.push_back({S[a] + 1, S[b]});//root->upd(S[a]+1, S[b], 1);
}

int query(int a, int b) {
    int res = 0;
    for (; head[a] != head[b]; b = up[head[b]]) {
        if (dep[head[a]] > dep[head[b]])
            swap(a, b);
        int cur_heavy_path_max = root->query(S[head[b]], S[b]);
        res += cur_heavy_path_max;
    }
    if (dep[a] > dep[b])
        swap(a, b);
    if(S[a] != S[b])res += root->query(S[a]+1, S[b]);
    return res;
}

int k;
int A[200005], B[200005];
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> q >> k;
	for(int i=1;i<n;i++){
		int x, y; cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
		A[i] = x, B[i] = y;
	}
	root= new node(1, n);
	dfs(1, -1, 1);
	//cerr << "ok\n";
	dfs2(1, 1, -1);
	while(q--){
		int x; cin >> x;
		int prv = -1;
		while(x--){
			int a; cin >> a;
			if(prv != -1)chng(prv, a);
			prv = a;
		}
		sort(upds.begin(), upds.end());
		int mx = 0;
		for(auto [i, j] : upds){
			if(mx >= j)continue;
			root->upd(max(mx + 1, i), j, 1);
			mx = max(mx, j);
		}
		upds.clear();
	}
	vector <int> ans;
	for(int i=1;i<n;i++){
		if(query(A[i], B[i]) >= k)ans.push_back(i);
	}
	cout << (int)ans.size() << '\n';
	for(auto i : ans)cout << 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