Submission #824252

#	Time	Username	Problem	Language	Result	Execution time	Memory
824252		Boomyday	Railway (BOI17_railway)	C++17	100 / 100	98 ms	32868 KiB

railway

//
// Created by adavy on 2/11/2023.
//
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+7; // 998244353;
const int MX = 1e5+5;
const int LG = 23;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!

int n, m, k, T=0;
int par[MX][LG]; // node, depth
int dep[MX], euler[MX];
vector<vi> adj(MX);
set<ii> paths;
vector<ii> pairs;
ll val[MX];


void dfs(int nd, int p=-1){
    euler[nd] = T++;
    par[nd][0] = p;
    if (nd!=0) dep[nd] = dep[p]+1;
    trav(v, adj[nd]){
        if(v != p){
            dfs(v, nd);
        }
    }
}

int lca(int a, int b){
    if (dep[a] < dep[b]) swap(a, b);
    int ddif = dep[a] - dep[b];
    F0R(j, LG) if ((1<<j)&ddif) a = par[a][j];
    if (a==b) return a;
    R0F(j, LG) if (par[a][j] != par[b][j]) {
        a = par[a][j];
        b = par[b][j];
    }
    return par[a][0];
}

void dfs2(int nd, int p=-1){

    trav(v, adj[nd]){
        if(v != p){

            dfs2(v, nd);
            if (val[v] >= 2*k){
                paths.insert({nd, v});
            }
            val[nd] += val[v];
        }
    }
}


int main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);

    cin >> n >> m >> k;
    memset(val, 0, sizeof(val));

    F0R(_, n-1){
        int a, b; cin >> a >> b;
        a--; b--;
        pairs.pb({a,b});
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dep[0] = 0;
    dfs(0);

    //cout << "________________" << endl;


    for(int j=1; j<LG;++j) F0R(i, n) par[i][j] = par[par[i][j-1]][j-1];


    F0R(_, m){
        int num; cin >> num;
        vi vals;
        F0R(i, num){
            int x; cin >> x; x--;
            vals.pb(x);
        }
        sort(all(vals), [](int a, int b){return euler[a]<euler[b];});
        vals.pb(vals[0]);
        F0R(i, num){
            int a = vals[i], b = vals[i+1];
            int l = lca(a,b);
            val[a]++; val[b]++;
            val[l] -= 2;
        }
    }
    //F0R(i, n) cout << val[i] << " ";
    //cout << endl;
    dfs2(0);
    //cout << paths.size() << endl;



    vi ans;
    F0R(i, n-1){
        int a = pairs[i].f, b = pairs[i].s;
        if (paths.count({a,b}) || paths.count({b,a})) ans.pb(i+1);


    }
    cout << ans.size() << endl;
    trav(i, ans) cout << i << " ";
    cout << endl;



}

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