제출 #1036664

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

#define pb push_back

using namespace std;

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

int n, q, k, timer, cnt[maxn], 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 p = 0){
    cnt[v] = a[v];
	for (auto [u, ind] : adj[v]){
	    if (u == p)
	        continue;
		dfs2(u, v);
		if (a[u] >= 2 * k)
		    res.pb(ind);
		a[v] += a[u];
	}
		
// 	cnt[p] += cnt[v];
// 	if (cnt[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}),
		adj[y].pb({x, i});
	dfs(1);
	for (int s, i = 0; i < q; i++){
		cin >> s;
		for (int x, i = 0; i < s; i++)
			cin >> x,
			check.pb({st[x], x});
		sort(check.begin(), check.end());
		for (int i = 0; i < s; i++){
			auto [v, u] = make_pair(check[i].second, check[(i + 1) % s].second);
			a[v]++;
			a[u]++;
			a[lca(v, u)] -= 2;
		}
		check.clear();
	}
	dfs2(1);
	cout << res.size() << '\n';
	for (auto e : res)
		cout << e + 1 << " ";
}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'void dfs2(int, int)':
railway.cpp:45:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   45 |      if (u == p)
      |      ^~
railway.cpp:47:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   47 |   dfs2(u, v);
      |   ^~~~
#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...