Submission #1253871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253871		ankite	Railway (BOI17_railway)	C++20	8 / 100	1096 ms	23972 KiB

railway

#include <bits/stdc++.h>;
#define int long long
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;

const int li = 2e5 + 10;
void print() { cerr << '\n'; }
template<typename T, typename... Args>
void print(T first, Args... rest) {
    cerr << first << ' ';
    print(rest...);
}

int n, m, k;
pii e[li];
vi qu[li], adj[li];

int cnt = 0, topo[li], max_child[li];
void build_dfs_tree(int node = 1) {
    topo[node] = ++cnt;
    max_child[node] = topo[node];

    for (int v : adj[node]) {
        if (!topo[v]) {
            build_dfs_tree(v);
            max_child[node] = max(max_child[node], max_child[v]);
        }
    }
}

int ecnt[li];

void solve1() {
    build_dfs_tree();

    int ans = 0;
    for (int i=1; i<=n-1; i++) {
        int u = e[i].first, v = e[i].second;
        int x = (topo[u] > topo[v] ? u : v);

        for (int j=1; j<=m; j++) {
            bool inside = 0, outside = 0;
            for (int nei : qu[j]) {
                if (topo[nei] >= topo[x]  &&  topo[nei] <= max_child[x]) inside = 1;
                else outside = 1;

                if (inside && outside) { ecnt[i]++; break; }
            }
        }

        if (ecnt[i] >= k) ans++;
    }

    cout << ans << '\n';
    for (int i=1; i<=n-1; i++) if (ecnt[i] >= k) cout << i << ' ';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for (int i=1, x, y; i<=n-1; i++) {
        cin >> x >> y;
        e[i] = {x, y};
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (int i=1; i<=m; i++) {
        int s, x; cin >> s;
        for (int j=1; j<=s; j++) { cin >> x; qu[i].push_back(x); }
    }
    solve1();

    return 0;
}

Compilation message (stderr)

railway.cpp:1:25: warning: extra tokens at end of #include directive
    1 | #include <bits/stdc++.h>;
      |                         ^

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