Submission #1189497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189497		quangnamoiracvl_ralaidecu	Railway (BOI17_railway)	C++20	23 / 100	1097 ms	39408 KiB

railway

// Codeforces Handle : thaonguyendethuongvai
// FB : Nuoc Khoang
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#define endl "\n"
#define tn int
#define pair pair< tn, tn >
#define fi first
#define se second
#define thaonguyen( i, a, b ) for( tn i = a; i <= b; i++ )
#define nguyenthao( i, a, b ) for( tn i = b; i >= a; i-- )
#define thaonguyenxinh ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const tn N = 1e5 + 5;
const tn M = __lg(2*N) + 2;
pair railway[N];
map< pair, tn > mp;
vector<tn> g[N], vertex, result;
tn n, q, k, u, v, z, tmc;
tn cnt[N], in[N], out[N], h[N], dp[N], valid[N], pp[N];
vector<tn> euler, depth;
tn first[N], logg[2 * N], st[2 * N][M];

void dfsEuler(tn u, tn par, tn d){
    first[u] = euler.size();
    euler.push_back(u);
    depth.push_back(d);
    for(tn v : g[u]){
        if(v == par) continue;
        pp[v] = u;
        dfsEuler(v, u, d + 1);
        euler.push_back(u);
        depth.push_back(d);
    }
}
void buildLCA(){
    tn sz = depth.size();
    logg[1] = 0;
    thaonguyen(i, 2, sz)
        logg[i] = logg[i/2] + 1;
    thaonguyen(i, 0, sz - 1)
        st[i][0] = i;
    for(tn j = 1; (1 << j) <= sz; j++){
        for(tn i = 0; i + (1 << j) <= sz; i++){
            tn x = st[i][j - 1];
            tn y = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = (depth[x] < depth[y] ? x : y);
        }
    }
}
tn lca(tn u, tn v){
    tn l = first[u], r = first[v];
    if(l > r) swap(l, r);
    tn j = logg[r - l + 1];
    tn x = st[l][j], y = st[r - (1 << j) + 1][j];
    return (depth[x] < depth[y] ? euler[x] : euler[y]);
}
bool cmp(tn a, tn b){
    return first[a] < first[b];
}
void floyd(tn u, tn par){
    dp[u] = valid[u];
    for(tn v : g[u]){
        if(v == par) continue;
        floyd(v, u);
        dp[u] += dp[v];
    }
}
void dijkstra(tn u, tn par){
    dp[u] = 0;
    valid[u] = 0;
    for(tn v : g[u]){
        if(v == par || !dp[v]) continue;
        cnt[v]++;
        dijkstra(v, u);
    }
}
signed main(){
    thaonguyenxinh;
    cin >> n >> q >> k;
    thaonguyen(i, 1, n - 1){
        cin >> u >> v;
        if(u > v) swap(u, v);
        mp[{u, v}] = i;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfsEuler(1, -1, 0);
    buildLCA();
    thaonguyen(j, 1, q){
        cin >> z;
        vertex.clear();
        if(z == 1) continue;
        thaonguyen(i, 1, z){
            cin >> u;
            valid[u] = 1;
            vertex.push_back(u);
        }
        sort(vertex.begin(), vertex.end(), cmp);
        thaonguyen(i, 0, z - 2)
            vertex.push_back(lca(vertex[i], vertex[i+1]));
        sort(vertex.begin(), vertex.end(), cmp);
        vertex.erase(unique(vertex.begin(), vertex.end()), vertex.end());

        floyd(vertex[0], -1);
        dijkstra(vertex[0], -1);
    }
    thaonguyen(i, 1, n){
        if(cnt[i] >= k){
            tn a = i, b = pp[i];
            if(a > b) swap(a, b);
            result.push_back(mp[{a, b}]);
        }
    }
    sort(result.begin(), result.end());
    cout << result.size() << endl;
    for(tn v : result) cout << v << " ";
}

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