Submission #647804

#	Time	Username	Problem	Language	Result	Execution time	Memory
647804		mychecksedad	Railway (BOI17_railway)	C++17	23 / 100	419 ms	63732 KiB

railway

/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;




int n, m, k, dep[N], co[N];
vector<pair<int, int>> g[N];
bitset<10005> marked, markede;
vector<pair<int, int>> path;
bool comp(int &a, int &b){
    return dep[a] < dep[b];
}
void pre(int v, int p){
    dep[v] = dep[p] + 1;
    for(auto u: g[v]) if(u.first != p) pre(u.first, v);
}
void dfs(int v, int p){
    for(auto u: g[v]){
        if(u.first != p){
            if(marked[u.first]){
                // cout << v << ' ' << u.first << '\n';
                int s = path.size() - 1;
                while(s >= 0 && !markede[path[s].second]){
                    co[path[s].second]++;
                    marked[path[s].first] = 1;
                    markede[path[s].second] = 1;
                    // cout << path[s].second << "g\n";
                    s--;
                }
            }
            path.pb(u);
            if(!markede[u.second])
                dfs(u.first, v);
            if(marked[u.first] && !markede[u.second]){
                markede[u.second] = 1, co[u.second]++; 
                // cout << u.first << ' ' << u.second << "f\n";
            }
            path.pop_back();
        }
    }
}
void solve(){
    cin >> n >> m >> k;
    for(int i = 0; i < n - 1; ++i){
        int u, v; cin >> u >> v;
        g[u].pb({v, i});
        g[v].pb({u, i});
        co[i] = 0;
    }
    dep[1] = 0;
    pre(1, 1);
    for(int i = 0; i < m; ++i){
        marked = markede = 0;
        int c; cin >> c;
        vector<int> v;
        for(int j = 0; j < c; ++j){
            int x; cin >> x;
            v.pb(x);
            marked[x] = 1;
        }
        for(int p: v) {path.pb({p, n}); dfs(p, p); path.pop_back();}
        // cout << '\n';
    }
    vector<int> ans;
    for(int i = 0; i < n - 1; ++i) if(co[i] >= k) ans.pb(i + 1);
    cout << ans.size() << '\n';
    for(int p: ans) cout << p << ' ';
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:91:16: warning: unused variable 'aa' [-Wunused-variable]
   91 |     int T = 1, aa;
      |                ^~

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