제출 #1036694

#제출 시각아이디문제언어결과실행 시간메모리
1036694sinatbtfardRailway (BOI17_railway)C++17
0 / 100
75 ms24272 KiB
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int maxn = 1e5 + 1, maxLg = 20;

int n, q, k, timer, a[maxn], h[maxn], st[maxn], fn[maxn], par[maxn][maxLg];
vector <pair <int, int>> adj[maxn], check;
vector <int> res;

void dfs (int v, int p = 0){
    st[v] = timer++;
    par[v][0] = p;
    for (int i = 1; i < maxLg; i++)
        par[v][i] = par[par[v][i - 1]][i - 1];
    for (auto [u, ind] : adj[v]){
        if (u != p){
            h[u] = h[v] + 1;
            dfs(u, v);
        }
    }
    fn[v] = timer++;
}

int lca (int x, int y){
	if (h[x] < h[y])
		swap(x, y);
	if (st[x] <= st[y] && fn[x] >= fn[y])
		return x;
	for (int i = maxLg - 1; i >= 0; i--){
		if (par[x][i] == 0)
			continue;
		int u = par[x][i];
		if (!(st[u] <= st[y] && fn[u] >= fn[y]))
			x = u;
	}
	return par[x][0];
}

void dfs2 (int v, int ind, int p = 0){
    for (auto [u, i] : adj[v])
        if (u != p)
            dfs2(u, i, v);
    a[p] += a[v];
    if (a[v] >= 2 * k && ind > -1)
        res.pb(ind);
}

int main (){
    ios_base::sync_with_stdio(0);
    cin >> n >> q >> k;
    for (int x, y, i = 0; i < n - 1; i++)
        cin >> x >> y,
        adj[x].pb({y, i + 1}),
        adj[y].pb({x, i + 1});
    dfs(1);
    for (int s, i = 0; i < q; i++){
        cin >> s;
        for (int x, j = 0; j < s; j++)
            cin >> x,
            check.pb({st[x], x});
        sort(check.begin(), check.end());
        for (int j = 0; j < s; j++){
            auto [v, u] = make_pair(check[j].second, check[(j + 1) % s].second);
			a[v]++;
			a[u]++;
			a[lca(v, u)] -= 2;
        }
        check.clear();
    }
    dfs2(1, -1);
    cout << res.size() << '\n';
    for (auto e : res)
        cout << e << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...