Submission #643710

#	Time	Username	Problem	Language	Result	Execution time	Memory
643710		ParsaS	Railway (BOI17_railway)	C++14	100 / 100	112 ms	25720 KiB

railway

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e5 + 5, MOD = 1e9 + 7, L = 20;
int n, m, k;
vector<pair<int, int> > adj[N];
vector<int> ans;
int dp[N], tin[N], tout[N], up[N][L];
int T;

void dfs(int v, int p) {
    up[v][0] = p;
    for (int l = 1; l < L; l++)
        up[v][l] = up[up[v][l - 1]][l - 1];
    tin[v] = ++T;
    for (auto [u, i] : adj[v]) {
        if (u != p)
            dfs(u, v);
    }
    tout[v] = ++T;
}
bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[v] >= tin[u];
}
int lca(int v, int u) {
    if (tin[v] > tin[u])
        swap(v, u);
    if (anc(v, u))
        return v;
    for (int l = L - 1; l >= 0; l--)
        if (!anc(up[v][l], u))
            v = up[v][l];
    return up[v][0];
}

void dfs2(int v, int p, int e) {
    for (auto [u, i] : adj[v]) {
        if (u != p) {
            dfs2(u, v, i);
            dp[v] += dp[u];
        }
    }
    if (dp[v] >= k)
        ans.pb(e);
}

void solve() {
    cin >> n >> m >> k;
    for (int i = 0; i < n - 1; i++) {
        int v, u; cin >> v >> u;
        adj[v].pb(mp(u, i + 1)), adj[u].pb(mp(v, i + 1));
    }
    dfs(1, 0);
    tout[0] = 1e9;
    for (int i = 0; i < m; i++) {
        int s; cin >> s;
        vector<pair<int, int> > vec;
        for (int j = 0; j < s; j++) {
            int v; cin >> v;
            vec.pb(mp(tin[v], v));
        }
        sort(vec.begin(), vec.end());
        int l2 = vec[0].se;
        for (int i = 1; i < s; i++) {
            int l = lca(vec[i].se, vec[i - 1].se);
            l2 = lca(l, l2);
            dp[l]--;
            dp[vec[i - 1].se]++;
        }
        dp[l2]--;
        dp[vec.back().se]++;
    }
    dfs2(1, 0, 0);
    cout << ans.size() << '\n';
    sort(ans.begin(), ans.end());
    for (auto x : ans)
        cout << x << ' ';
    cout << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();

    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:21:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for (auto [u, i] : adj[v]) {
      |               ^
railway.cpp: In function 'void dfs2(int, int, int)':
railway.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for (auto [u, i] : adj[v]) {
      |               ^

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