Submission #647861

#	Time	Username	Problem	Language	Result	Execution time	Memory
647861		mychecksedad	Railway (BOI17_railway)	C++17	100 / 100	135 ms	48764 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, co[N], up[N][K], timer = 0, in[N], out[N];
vector<pair<int, int>> g[N];
vector<int> qq(N);
void pre(int v, int p){
    in[v] = timer++;
    up[v][0] = p;
    for(auto u: g[v]){
        if(u.first != p){
            pre(u.first, v);
        }
    }
    out[v] = timer++;
}
bool is_ancestor(int u, int v){
    return in[u] <= in[v] && out[v] <= out[u]; 
}
int lca(int u, int v){
    if(is_ancestor(u, v)) return u;
    if(is_ancestor(v, u)) return v;
    for(int j = K - 1; j >= 0; --j){
        if(!is_ancestor(up[u][j], v)) u = up[u][j];
    }
    return up[u][0];
}
void dfs(int v, int p, int e){
    for(auto u: g[v]){
        if(u.first != p){
            dfs(u.first, v, u.second);
            qq[v] += qq[u.first];
        }
    }
    co[e] = qq[v];
}
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;
    }
    pre(1, 1);
    for(int j = 1; j < K; ++j){
        for(int i = 1; i <= n; ++i) up[i][j] = up[up[i][j - 1]][j - 1];
    }
    for(int i = 0; i < m; ++i){
        int c; cin >> c;
        vector<int> v;
        for(int j = 0; j < c; ++j){
            int x; cin >> x; v.pb(x);
        }
        sort(all(v), [&](const int &a, const int &b){
            return in[a] < in[b];
        });
        for(int j = 0; j < c; ++j){
            int s = v[j], e = v[(j+1)%c];
            int lc = lca(s, e);
            qq[lc] -= 2;
            qq[s]++, qq[e]++;
        }
    }
    dfs(1, 1, n);

    vector<int> ans;
    for(int i = 0; i < n - 1; ++i) if(co[i] >= 2*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:96:16: warning: unused variable 'aa' [-Wunused-variable]
   96 |     int T = 1, aa;
      |                ^~

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