Submission #654543

#	Time	Username	Problem	Language	Result	Execution time	Memory
654543		esomer	Railway (BOI17_railway)	C++17	23 / 100	1094 ms	62600 KiB

railway

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

const int MOD = 998244353;

vector<int> ans;

pair<set<int>, map<int, int>> DFS(int x, vector<vector<pair<int, int>>>& adj, vector<vector<int>>& mn, vector<int>& cnt, int p, int id, int k){
    set<int> pos;
    map<int, int> m;
    for(int y : mn[x]){
        if(cnt[y] != 1){
            m[y]++;
            pos.insert(y);
        }
    }
    for(auto pr : adj[x]){
        int node = pr.first;
        if(node == p) continue;
        auto t = DFS(node, adj, mn, cnt, x, pr.second, k);
        if(x != 0){
            if((int)pos.size() < (int)t.first.size()) swap(pos, t.first);
            for(auto x : t.first){
                pos.insert(x);
            }
            if((int)m.size() < (int)t.second.size()) swap(m, t.second);
            for(auto pr : t.second){
                m[pr.first] += pr.second;
                int y = m[pr.first];
                if(y == cnt[pr.first]) {pos.erase(pr.first); m.erase(pr.first);}
            }
        }
    }
    if(x != 0){
        if((int)pos.size() >= k) ans.push_back(id);
    }
    return {pos, m};
}

void solve(){
    int n, m, k; cin >> n >> m >> k;
    vector<vector<pair<int, int>>> adj(n);
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b; a--; b--;
        adj[a].push_back({b, i + 1}); adj[b].push_back({a, i + 1});
    }
    vector<vector<int>> mn(n);
    vector<int> cnt(m);
    for(int i = 0; i < m; i++){
        int s; cin >> s;
        set<int> st;
        while(s--){
            int x; cin >> x; x--;
            bool good = st.count(x);
            if(!good){
                st.insert(x);
                mn[x].push_back(i);
            }
        }
        cnt[i] = (int)st.size();
    }
    DFS(0, adj, mn, cnt, -1, -1, k);
    sort(ans.begin(), ans.end()); cout << ans.size() << endl; for(int x : ans) {cout << x << " ";} cout << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    //int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        //cout << "Case #"<<t << ": ";
        solve();
    }
}

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