제출 #1160048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160048		Hamed_Ghaffari	Railway (BOI17_railway)	C++20	100 / 100	64 ms	24016 KiB

railway

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

using pii = pair<int, int>;

#define pb push_back
#define all(x) x.begin(), x.end()

const int MXN = 1e5+5;
const int LOG = 17;

int n, par[LOG][MXN], stt[MXN], fnt[MXN], timer;
vector<pii> g[MXN];

void dfs(int v) {
    for(int i=1; i<LOG; i++)
        par[i][v] = par[i-1][par[i-1][v]];
    stt[v] = timer++;
    for(auto [u, i] : g[v])
        if(u!=par[0][v])
            par[0][u]=v,
            dfs(u);
    fnt[v] = timer;
}
bool is_anc(int u, int v) { return stt[u]<=stt[v] && fnt[v]<=fnt[u]; };
int LCA(int u, int v) {
    if(is_anc(u, v)) return u;
    for(int i=LOG-1; i>=0; i--)
        if(par[i][u] && !is_anc(par[i][u], v))
            u = par[i][u];
    return par[0][u];
}

int k, ans[MXN];
void upd(int u, int v) {
    ans[u]++;
    ans[v]++;
    ans[LCA(u,v)] -= 2;
}

vector<int> res;

void DFS(int v) {
    for(auto [u, i] : g[v])
        if(u!=par[0][v]) {
            DFS(u);
            if(ans[u]>=2*k) res.pb(i);
            ans[v] += ans[u];
        }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int m;
    cin >> n >> m >> k;
    for(int i=0, u,v; i<n-1;i ++) {
        cin >> u >> v;
        g[u].pb(pii(v, i+1));
        g[v].pb(pii(u, i+1));
    }
    dfs(1);
    for(int t=0, s; t<m; t++) {
        cin >> s;
        vector<int> V(s);
        for(int &v : V) cin >> v;
        sort(all(V), [&](int u, int v) { return stt[u] < stt[v]; });
        for(int i=0; i+1<s; i++)
            upd(V[i], V[i+1]);
        upd(V[0], V[s-1]);
    }
    DFS(1);
    cout << res.size() << '\n';
    sort(all(res));
    for(int i : res) cout << i << ' ';
    cout << '\n';
    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