Submission #484231

#	Time	Username	Problem	Language	Result	Execution time	Memory
484231		MohamedFaresNebili	Railway (BOI17_railway)	C++14	0 / 100	1090 ms	25788 KiB

railway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
/// #include "messy.h"

        using namespace std;
        using namespace __gnu_pbds;

        using ll  = long long;
        using ld  = long double;
        using ii  = pair<ll, ll>;
        using ull = unsigned long long;

        using vl  = vector<long long>;

        #define mp make_pair
        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define ub upper_bound
        #define all(x) (x).begin() , (x).end()
        #define vi vector<int>

        const int N = 2*100005;
        const long long MOD = 1000000007;
        const long double EPS = 0.000000001;
        const double PI = 3.14159265358979323846;
        const long long INF = 10000000000000000;
        const int nx[2]={1, 0}, ny[2]={0, 1};

        long long gcd(int a, int b) { return (b==0?a:gcd(b, a%b)); }
        long long lcm(int a, int b) { return  a*(b/gcd(a, b)); }
        long long fact(int a) { return (a==1?1:a*fact(a-1)); }

        template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

        int n, m, k, freq[5*100005], vis[5*100005], d[5*100005]; ii par[5*100005]; 
        vector<ii>adj[5*100005]; bool done[5*200005];
        void dfs(int v, int p = 1) {
            for(auto to: adj[v]) {
                int u = to.ff;
                if(u == p) continue;
                par[u] = {v, to.ss}; d[u] = d[v]+1;
                dfs(u, v);
            }
        }
        bool dfs0(int v, int to) {
            if(v == to || v == 1) return (v == to);
            if(!vis[par[v].ss]) vis[par[v].ss]=1, freq[par[v].ss]++;
            if(freq[par[v].ss]==k) done[par[v].ss]=1, freq[par[v].ss]=0;
            return dfs0(par[v].ff, to);
        }
        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            /// freopen("in.txt", "r", stdin);
            cin >> n >> m >> k;
            for(int l = 1; l < n; l++) {
                int a, b; cin>>a>>b;
                adj[a].pb({b, l}); adj[b].pb({a, l});
            }
            dfs(1); vector<int> res;
            while(m--) {
                int c; cin>>c; vector<int>arr;
                for(int l=0;l<c;l++) {
                    int a; cin>>a; arr.pb(a);
                }
                memset(vis, 0, sizeof vis);
                for(int l = 0; l < c; l++) {
                    for(int i = l + 1; i < c; i++ ){
                        int from = arr[l], to = arr[i];
                        if(d[from] < d[to]) swap(from, to);
                        if(!dfs0(from, to)) {
                            dfs0(to, from);
                        }
                    }
                }
            }
            for(int l = 1; l < n; l++) {
                if(done[l]) res.pb(l);
            }
            cout << (int)res.size() << "\n";
            for(auto u: res) cout << u << " ";
            return 0;
        }

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