Submission #487547

#	Time	Username	Problem	Language	Result	Execution time	Memory
487547		alireza_kaviani	Railway (BOI17_railway)	C++11	30 / 100	1081 ms	31800 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "
 
constexpr int N = 1e5 + 10, M = 5e4 + 10;
 
int n, k, m, pe[N], sz[N];
int init[N], cnt[M], cnt0, cntf;
vector<int> *st[N];
vector<int> col[N], ge[N], g[N], ans;
 
void prep(int v, int p, int pi) {
    pe[v] = pi;
    int i = 0;
    sz[v] = 1;
    for (auto &u : g[v]) {
        if (u != p) {
            prep(u, v, ge[v][i]);
            sz[v] += sz[v];
        }
        ++i;
    }
}
 
void dfs(int v, int p, bool keep) {
    int bg = -1, bgs = 0;
    for (auto &u : g[v]) {
        if (u != p && sz[u] > bgs) {
            bgs = sz[u];
            bg = u;
        }
    }
    if (bg == -1) {
        st[v] = new vector<int>();
        st[v]->push_back(v);
    } else {
        for (auto &u : g[v]) {
            if (u != p && u != bg) {
                dfs(u, v, false);
            }
        }
        dfs(bg, v, true);
        st[v] = st[bg];
        st[v]->push_back(v);
        for (auto &u : g[v]) {
            if (u != p && u != bg) {
                for (auto &w : *st[u]) {
                    st[v]->push_back(w);
                    for (auto &c : col[w]) {
                        if (++cnt[c] == init[c]) {
                            cntf++;
                        }
                        if (cnt[c] == 1) {
                            cnt0--;
                        }
                    }
                }
                delete st[u];
            }
        }
    }
    for (auto &c : col[v]) {
        if (++cnt[c] == init[c]) {
            cntf++;
        }
        if (cnt[c] == 1) {
            cnt0--;
        }
    }
    if (m - cnt0 - cntf >= k) {
        ans.push_back(pe[v]);
    }
    //cerr << v << ' ' << cnt0 << ' ' << cntf << '\n';
    if (!keep) {
        for (auto &u : *st[v]) {
            for (auto &c : col[u]) {
                if (--cnt[c] == 0) {
                    cnt0++;
                }
                if (cnt[c] == init[c] - 1) {
                    cntf--;
                }
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
     
    cin >> n >> m >> k;
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].push_back(u);
        g[u].push_back(v);
        ge[v].push_back(i);
        ge[u].push_back(i);
    }
    for (int i = 0; i < m; ++i) {
        int s;
        cin >> s;
        cnt[i] = 0;
        init[i] = s;
        if (!s) {
            ++cntf;
        }
        ++cnt0;
        while (s--) {
            int v;
            cin >> v;
            --v;
            col[v].push_back(i);
        }
    }
 
    prep(0, -1, -1);
    dfs(0, -1, true);
 
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (auto &e : ans) {
        cout << e + 1 << ' ';
    }
}

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