Submission #1189484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189484		quangnamoiracvl_ralaidecu	Railway (BOI17_railway)	C++20	23 / 100	1098 ms	29256 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(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 ){
    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 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 or !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);
    }
    bfs( 1, -1 ); initialize();
    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 );
        floyd( vertex[0], pp[vertex[0]] );
        dijkstra( vertex[0], pp[vertex[0]] );
    }
    thaonguyen( i, 1, n )
        if ( cnt[i] >= k ){
            tn a = i; tn 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