Submission #1189475

#TimeUsernameProblemLanguageResultExecution timeMemory
1189475quangnamoiracvl_ralaidecuRailway (BOI17_railway)C++20
0 / 100
2 ms2628 KiB
#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 ){ 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; freopen( "Railway.inp", "r", stdin ); freopen( "Railwat.out", "w", stdout ); 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 << " "; }

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen( "Railway.inp", "r", stdin );
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     freopen( "Railwat.out", "w", stdout );
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...