Submission #1189447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189447		quangnamoiracvl_ralaidecu	Railway (BOI17_railway)	C++20	0 / 100	62 ms	29780 KiB

railway

// Author : Thao Nguyen De Thuong Vai 
// FB : Nuoc Khoang 
#include<bits/stdc++.h>
using namespace std;
#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(N) + 1;
pair railway[N];
map< pair, tn > mp;
vector<tn> g[N], vertex, result;
tn n, q, k, u, v, z, tmc, cnt[N], in[N], out[N], h[N], p[N][M], dp[N], valid[N], pp[N];
void bfs( tn u, tn par ){
    dp[u] = valid[u];
    in[u] = out[u] = ++tmc;
    for( tn v : g[u] ){
        if ( v == par )
            continue;
        pp[v] = u;
        h[v] = h[u] + 1;
        bfs( v, u );
        dp[u] += dp[v];
        p[v][0] = u;
        out[u] = max( out[u], out[v] );
    }
}
void initialize(){
        thaonguyen( j, 1, __lg(n) )
            thaonguyen( i, 1, n )
                p[i][j] = p[p[i][j-1]][j-1];
}
tn lca( tn u, tn v ){
    if ( h[u] < h[v] )
        swap( u, v );
    tn z = __lg( h[u] );
    nguyenthao( i, 0, z )
        if ( h[u] - h[v] >= ( 1 << i ) )
            u = p[u][i];
    if ( u == v )
        return u;
    nguyenthao( i, 0, z )
        if ( p[u][i] != p[v][i] )
            u = p[u][i],
            v = p[v][i];
    return p[u][0];
}
bool cmp( tn a, tn b ){
    return in[a] < in[b];
}
void dijkstra( tn u, tn par ){
    for( tn v : g[u] ){
        if ( v == par or !dp[v] )
            continue;
        tn a = u; tn b = v;
        if ( a > b )
            swap( a, b );
        result.push_back( mp[ { a, b } ] );
        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);
        railway[i] = { u, v };
    }
    while( q-- ){
         cin >> z;
        thaonguyen( i, 1, z ){
            cin >> u, cnt[u]++;
            if ( cnt[u] == k ){
                    tn a = railway[u].fi;
                    tn b = railway[u].se;
                    valid[a] = 1; valid[b] = 1;
                    vertex.push_back(a); vertex.push_back(b);
            }
        }
    }
    bfs( 1, -1 );
    sort( vertex.begin(), vertex.end(), cmp );
    tn mz = vertex.size() - 2;
    thaonguyen( i, 0, mz )
        vertex.push_back( lca( vertex[i], vertex[i+1] ) );
    sort( vertex.begin(), vertex.end(), cmp );
    dijkstra( vertex[0], pp[vertex[0]] );
    cout << result.size() << endl;
    for( tn v : result )
        cout << v << " ";
}

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