Submission #1253872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253872		ankite	Railway (BOI17_railway)	C++20	23 / 100	1097 ms	35848 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 << ' ';
}

int dfscnt[li], choose[li];
vi g[li];
bool vis[li];
void _dfs(int s, int node = 1) {
//    print("    ", node);
    vis[node] = 1;
    if (choose[node] > 0) dfscnt[node] += choose[node];

    for (int ee : g[node]) {
        pii other = e[ee];
        int v = other.first + other.second - node;

        if (!vis[v]) {
            _dfs(s, v);
            if (dfscnt[v] > 0  &&  dfscnt[v] < s) ecnt[ee]++;

            dfscnt[node] += dfscnt[v];
        }
    }
//    print("         ",node,  dfscnt[node]);
}

void solve2() {
    for (int i=1; i<=m; i++) {
//        print(i);
        memset(vis, 0, sizeof(vis));
        memset(choose, 0, sizeof(choose));
        memset(dfscnt, 0, sizeof(dfscnt));
        for (int cur : qu[i]) choose[cur]++;


        _dfs(qu[i].size());
    }

    int ans = 0;
    for (int i=1; i<=n-1; i++) 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);
        g[x].push_back(i);
        g[y].push_back(i);
    }
    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); }
    }
    solve2();

    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: 15 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25