제출 #502659

#제출 시각아이디문제언어결과실행 시간메모리
502659sumit_kk10Railway (BOI17_railway)C++17
23 / 100
152 ms32244 KiB
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
#define F first 
#define S second
using namespace std;
const int N = 100005, MOD = 1e9 + 7;
vector<ll> graph[N];
ll pre[N], dp[N][(ll) log2(100005)], n, m, s, lvl[N], tin[N], tout[N], timer = 0, u[N], v[N], fenwick[N];
 
void dfs(int source, int par, int level){
	dp[source][0] = par;
	lvl[source] = level;
	tin[source] = ++timer;
	for(auto k : graph[source])
		if(k != par)
			dfs(k, source, level + 1);
	tout[source] = timer;
}
 
void init(){
	dfs(1, -1, 0);
	for(int i = 1; i <= (log2(n)); ++i)
		for(int j = 1; j <= n; ++j)
			if(dp[j][i - 1] != -1)
				dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
 
ll LCA(int u, int v){
	if(lvl[u] > lvl[v]) swap(u, v);
	ll d = lvl[v] - lvl[u];
	while(d){
		int jump = log2(d);
		v = dp[v][jump];
		d -= pow(2, jump);
	}
	if(v == u) 
		return v;
	for(int i = log2(n); i >= 0; --i){
		if(dp[v][i] != -1 && dp[v][i] != dp[u][i]){
			u = dp[u][i];
			v = dp[v][i];
		}
	}
	return dp[v][0];
}
 
int get(int node){
	int ans = 0;
	for(int i = node; i >= 1; i -= (i & -i))
		ans += fenwick[i];
	return ans;
}
 
void upd(int node, int val){
	for(int i = node; i <= n; i += (i & -i))
		fenwick[i] += val;
}

bool cmp(int x, int y){
	return tin[x] < tin[y];
}

void edges(int node, int par){
	for(auto k : graph[node]){
		if(k == par) continue;
		edges(k, node);
		pre[node] += pre[k];
	}
}

void solve(){
	cin >> n >> m >> s;
	for(int i = 1; i <= n - 1; ++i){
		cin >> u[i] >> v[i];
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
	}
	memset(dp, -1, sizeof dp);
	init();
	while(m--){
		int r;
		cin >> r;
		vector<int> a;
		for(int i = 0; i < r; ++i){
			int x;
			cin >> x;
			a.push_back(x);
		}
		sort(a.begin(), a.end(), cmp);
		a.push_back(a[0]);
		for(int i = 0; i < r; ++i){
			int p = LCA(a[i], a[i + 1]);
			pre[a[i]]++;
			pre[a[i + 1]]++;
			pre[p] -= 2;
		}
	}
	edges(1, 0);
	vector<int> ans;
	for(int i = 1; i <= n - 1; ++i){
		if(lvl[u[i]] > lvl[v[i]])
			swap(u[i], v[i]);
		int x = pre[v[i]];
		if(x >= 2*s)
			ans.push_back(i);
	}
	cout << ans.size() << '\n';
	for(auto k : ans) cout << k << ' ';
}
 
int main() {
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
    	solve();
	return 0;
}

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

railway.cpp: In function 'int main()':
railway.cpp:116:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  116 |     while(t--)
      |     ^~~~~
railway.cpp:118:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  118 |  return 0;
      |  ^~~~~~
#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...