제출 #1306244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306244		Robert_junior	Railway (BOI17_railway)	C++20	36 / 100	58 ms	34732 KiB

railway

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define F first
#define S second
#define bt bitset<5010>
const int N = 1e5 + 100, K = 1610;
const int mod = 998244353;
vector<pair<int, int>>g[N];
vector<int>g1[N];
int tin[N], tout[N], timer, up[N][20], bc[N], head[N], sz[N], pf[N], cnt[N];
int n, m, k;
void init(int v, int p){
    sz[v] = 1;
    for(auto [to, idx] : g[v]){
        if(to == p) continue;
        init(to, v);
        sz[v] += sz[to];
        if(sz[to] > sz[bc[v]]) bc[v] = to;
    }
}
void dfs(int v, int p){
    tin[v] = ++timer;
	up[v][0] = p;
	for(int i = 1; i < 20; i++){
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	if(bc[v]){
	    head[bc[v]] = head[v];
	    dfs(bc[v], v);
	}
	for(auto [to, idx] : g[v]){
		if(to == p || to == bc[v]) continue;
		head[to] = to;
		dfs(to, v);
	}
	tout[v] = timer;
}
int F(int u, int v){
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v){
	if(F(u, v)) return u;
	if(F(v, u)) return v;
	for(int i = 19; i >= 0; i--){
		if(!F(up[u][i], v)) u = up[u][i];
	}
	return up[u][0];
}
bool cmp(int x, int y){
	return tin[x] < tin[y];
}
void dfs2(int v, int p){
    for(auto [to, idx] : g[v]){
        if(to == p) continue;
        dfs2(to, v);
        sz[v] += sz[to];
    }
}
void solve(){
	cin>>n>>m>>k;
	for(int i = 1; i <= n - 1; i++){
		int u, v;
		cin>>u>>v;
		g[u].pb({v, i});
		g[v].pb({u, i});
	}
	init(1, 1);
	head[1] = 1;
	dfs(1, 1);
	for(int i = 1; i <= n; i++) sz[i] = 0;
	for(int i = 1; i <= m; i++){
		vector<int>v;
		int z;
		cin>>z;
		for(int j = 1; j <= z; j++){
			int x;
			cin>>x;
			v.pb(x);
		}
		sort(all(v), cmp);
		v.pb(v[0]);
		for(int i = 0; i < z; i++){
		    sz[v[i]]++;
		    sz[v[i + 1]]++; 
		    sz[lca(v[i], v[i + 1])] -= 2;
		}
	}
	dfs2(1, 1);
	vector<int>ans;
	for(int i = 2; i <= n; i++){
		if(sz[i] >= 2 * k){
		    for(auto [to, idx] : g[i]){
		        if(to == up[i][0]) ans.pb(idx);
		    }
		}
	}
	cout<<ans.size()<<'\n';
	for(auto it : ans) cout<<it<<' ';
}
main(){
	ios_base :: sync_with_stdio(false); 
	cin.tie(nullptr);
	int t = 1;
	//cin>>t;
	while(t--){
		solve();
	}
}

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

railway.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  105 | main(){
      | ^~~~

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