Submission #1189517

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

railway

// Codeforces Handle : thaonguyendethuongvai
// FB : Nuoc Khoang
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC target ("avx,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;
vector<tn> euler;
tn high[N], pos[N], minHigh[2 * N][20];
tn n, q, k, u, v, z;
tn cnt[N], dp[N], valid[N], pp[N];

void dfs(int u, int par) {
    pos[u] = euler.size();
    euler.push_back(u);
    for (int v : g[u]) {
        if (v == par) continue;
        high[v] = high[u] + 1;
        pp[v] = u;
        dfs(v, u);
        euler.push_back(u);
    }
}
tn MIN_HIGH(tn x, tn y) {
    return high[x] < high[y] ? x : y;
}
void buildLCA() {
    tn sz = euler.size();
    for (tn i = 0; i < sz; i++) minHigh[i][0] = euler[i];
    for (tn j = 1; (1 << j) <= sz; j++)
        for (tn i = 0; i + (1 << j) <= sz; i++)
            minHigh[i][j] = MIN_HIGH(minHigh[i][j - 1], minHigh[i + (1 << (j - 1))][j - 1]);
}
tn lca(tn u, tn v) {
    tn pu = pos[u], pv = pos[v];
    if (pu > pv) swap(pu, pv);
    tn k = 31 - __builtin_clz(pv - pu + 1);
    return MIN_HIGH(minHigh[pu][k], minHigh[pv - (1 << k) + 1][k]);
}

bool cmp(tn a, tn b){
    return pos[a] < pos[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);
    }

    dfs(1, -1);
    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