제출 #333219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333219		limabeans	Railway (BOI17_railway)	C++17	100 / 100	281 ms	53228 KiB

railway

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl










const int maxn = 1e5+10;



int n, m, k;
vector<pair<int,int>> g[maxn];
set<int> nodes[maxn];

const int LOG = 19;

int par[LOG+1][maxn];
int dep[maxn];


int lca(int u, int v) {
    if (dep[u]<dep[v]) swap(u,v);
    int dx = dep[u]-dep[v];
    for (int j=0; j<LOG; j++) {
	if (dx>>j&1) {
	    u = par[j][u];
	}
    }

    if (u==v) return v;

    for (int j=LOG-1; j>=0; j--) {
	if (par[j][u] != par[j][v]) {
	    u = par[j][u];
	    v = par[j][v];
	}
    }

    return par[0][u];
}

int tin[maxn];
int tout[maxn];
int cloc = 1;

void dfs(int at, int p) {
    for (int j=1; j<LOG; j++) {
	par[j][at] = par[j-1][par[j-1][at]];
    }

    tin[at] = cloc++;
    
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	dep[to]=1+dep[at];
	par[0][to] = at;
	dfs(to, at);
    }

    tout[at] = cloc++;
}


vector<int> add[maxn], sub[maxn];


vector<int> ans;

set<int> dfs2(int at, int p, int edId=0) {
    set<int> res;
    for (auto ed: g[at]) {
	int idx = ed.first;
	int to = ed.second;
	if (to==p) continue;
	auto ret = dfs2(to, at, idx);
	if (res.size() < ret.size()) {
	    swap(res, ret);
	}
	res.insert(ret.begin(), ret.end());
    }

    for (int x: add[at]) {
	res.insert(x);
    }

    for (int x: sub[at]) {
	res.erase(x);
    }

    if ((int)res.size() >= k && edId!=0) ans.push_back(edId);

    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m>>k;
    for (int i=1; i<n; i++) {
	int u,v; cin>>u>>v;
	g[u].push_back({i,v});
	g[v].push_back({i,u});
    }

    
    for (int i=1; i<=m; i++) {
	int t;
	cin>>t;
	while (t--) {
	    int x;
	    cin>>x;
	    nodes[i].insert(x);
	}
    }

    dfs(1,0);

    for (int i=1; i<=m; i++) {
	int top = *nodes[i].begin();
	for (int x: nodes[i]) {
	    add[x].push_back(i);
	    top = lca(top, x);
	}
	sub[top].push_back(i);
    }

    dfs2(1,0);


    cout<<ans.size()<<endl;
    sort(ans.begin(),ans.end());
    for (int i: ans) cout<<i<<" ";
    cout<<endl;
    
    
    return 0;
}

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