Submission #927795

#	Time	Username	Problem	Language	Result	Execution time	Memory
927795		Amirreza_Fakhri	Railway (BOI17_railway)	C++17	100 / 100	106 ms	23756 KiB

railway

// In the name of the God
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 1e5+5, lg = 17;

int n, m, k, t = 0, in[maxn], out[maxn], cnt[maxn], par[lg][maxn];
vector <int> vec;
vector <pii> adj[maxn];

bool cmp(int v, int u) {
    return in[v] < in[u];
}

void dfs1(int v, int p) {
    in[v] = t++;
    par[0][v] = p;
    for (int i = 1; i < lg; i++) par[i][v] = par[i-1][par[i-1][v]];
    for (pii e : adj[v]) {
        if (e.F != p) dfs1(e.F, v);
    }
    out[v] = t;
}

bool is(int v, int u) {
    return in[v] <= in[u] and out[v] >= out[u];
}

int lca(int v, int u) {
    if (is(v, u)) return v;
    if (is(u, v)) return u;
    for (int i = lg-1; i >= 0; i--) {
        if (!is(par[i][v], u)) v = par[i][v];
    }
    return par[0][v];
}

void dfs2(int v, int p, int ed) {
    for (pii e : adj[v]) {
        if (e.F != p) {
            dfs2(e.F, v, e.S);
            cnt[v] += cnt[e.F];
        }
    }
    if (cnt[v] >= k) vec.pb(ed);
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int v, u; cin >> v >> u;
        adj[--v].pb(mp(--u, i));
        adj[u].pb(mp(v, i));
    }
    dfs1(0, 0);
    for (int i = 0; i < m; i++) {
        int s; cin >> s;
        for (int j = 0; j < s; j++) {
            int v; cin >> v;
            cnt[--v]++;
            vec.pb(v);
        }
        sort(all(vec), cmp);
        for (int i = 1; i < s; i++) cnt[lca(vec[i], vec[i-1])]--;
        cnt[lca(vec[0], vec[s-1])]--;
        vec.clear();
    }
    dfs2(0, 0, 0);
    sort(all(vec));
    cout << vec.size() << '\n';
    for (int e : vec) cout << e << ' ';
    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