# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
629685 |
2022-08-14T22:02:53 Z |
chonka |
Railway (BOI17_railway) |
C++17 |
|
138 ms |
25284 KB |
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MAXN = 1e5 + 7 ;
const int LOG = 17 ;
int n , m , k ;
vector < pair < int , int > > v[ MAXN ] ;
int prv_id[ MAXN ] ;
int lvl[ MAXN ] ;
int LCA[ MAXN ][ LOG ] ;
int st[ MAXN ] , en[ MAXN ] ;
int add[ MAXN ] , tp ;
void init ( int x , int prv ) {
st[ x ] = ++ tp ;
for ( int i = 1 ; i < LOG ; ++ i ) {
LCA[ x ][ i ] = LCA[ LCA[ x ][ i - 1 ] ][ i - 1 ] ;
}
for ( auto [ y , id ] : v[ x ] ) {
if ( y == prv ) { continue ; }
prv_id[ y ] = id ;
LCA[ y ][ 0 ] = x ;
lvl[ y ] = lvl[ x ] + 1 ;
init ( y , x ) ;
}
en[ x ] = tp ;
}
int get_lca ( int x , int y ) {
for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
if ( lvl[ x ] - ( 1 << i ) >= lvl[ y ] ) {
x = LCA[ x ][ i ] ;
}
if ( lvl[ y ] - ( 1 << i ) >= lvl[ x ] ) {
y = LCA[ y ][ i ] ;
}
}
for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
if ( LCA[ x ][ i ] != LCA[ y ][ i ] ) {
x = LCA[ x ][ i ] , y = LCA[ y ][ i ] ;
}
}
if ( x != y ) { x = LCA[ x ][ 0 ] ; }
return x ;
}
bool is_anc ( int up , int down ) {
return ( st[ up ] <= st[ down ] && en[ down ] <= en[ up ] ) ;
}
int aux[ 2 * MAXN ] ;
vector < int > ans ;
void dfs ( int x , int prv ) {
for ( auto [ y , id ] : v[ x ] ) {
if ( y == prv ) { continue ; }
dfs ( y , x ) ;
add[ x ] += add[ y ] ;
}
}
void solve ( ) {
cin >> n >> m >> k ;
for ( int i = 1 , x , y ; i < n ; ++ i ) {
cin >> x >> y ;
v[ x ].push_back ( { y , i } ) ;
v[ y ].push_back ( { x , i } ) ;
}
init ( 1 , -1 ) ;
stack < int > s ;
auto cmp = [ & ] ( int x , int y ) {
return ( st[ x ] < st[ y ] ) ;
};
while ( m -- ) {
int sz ; cin >> sz ;
for ( int i = 1 ; i <= sz ; ++ i ) {
cin >> aux[ i ] ;
}
sort ( aux + 1 , aux + sz + 1 , cmp ) ;
while ( s.empty ( ) == false ) { s.pop ( ) ; }
tp = sz ;
for ( int i = 1 ; i < sz ; ++ i ) {
aux[ ++ tp ] = get_lca ( aux[ i ] , aux[ i + 1 ] ) ;
}
sz = tp ;
sort ( aux + 1 , aux + sz + 1 , cmp ) ;
s.push ( aux[ 1 ] ) ;
for ( int i = 2 ; i <= sz ; ++ i ) {
while ( is_anc ( s.top ( ) , aux[ i ] ) == false ) {
int leaf = s.top ( ) ; s.pop ( ) ;
++ add[ leaf ] , -- add[ s.top ( ) ] ;
}
s.push ( aux[ i ] ) ;
}
while ( 1 ) {
int leaf = s.top ( ) ; s.pop ( ) ;
if ( s.empty ( ) == true ) { break ; }
int root = s.top ( ) ;
++ add[ leaf ] , -- add[ root ] ;
}
}
dfs ( 1 , -1 ) ;
for ( int i = 2 ; i <= n ; ++ i ) {
if ( add[ i ] >= k ) {
ans.push_back ( prv_id[ i ] ) ;
}
}
sort ( ans.begin ( ) , ans.end ( ) ) ;
int sz = ans.size ( ) ;
cout << sz << "\n" ;
for ( auto x : ans ) {
cout << x << " " ;
}
cout << "\n" ;
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
7 ms |
3924 KB |
Output is correct |
3 |
Correct |
6 ms |
3924 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
4492 KB |
Output is correct |
7 |
Correct |
6 ms |
4096 KB |
Output is correct |
8 |
Correct |
5 ms |
3956 KB |
Output is correct |
9 |
Correct |
8 ms |
4076 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
3 ms |
2676 KB |
Output is correct |
14 |
Correct |
2 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
7 ms |
3924 KB |
Output is correct |
3 |
Correct |
6 ms |
3924 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
4492 KB |
Output is correct |
7 |
Correct |
6 ms |
4096 KB |
Output is correct |
8 |
Correct |
5 ms |
3956 KB |
Output is correct |
9 |
Correct |
8 ms |
4076 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
3 ms |
2676 KB |
Output is correct |
14 |
Correct |
2 ms |
2680 KB |
Output is correct |
15 |
Correct |
35 ms |
4388 KB |
Output is correct |
16 |
Correct |
28 ms |
4352 KB |
Output is correct |
17 |
Correct |
31 ms |
4400 KB |
Output is correct |
18 |
Correct |
6 ms |
4436 KB |
Output is correct |
19 |
Correct |
6 ms |
4108 KB |
Output is correct |
20 |
Correct |
27 ms |
4532 KB |
Output is correct |
21 |
Correct |
31 ms |
4520 KB |
Output is correct |
22 |
Correct |
2 ms |
2644 KB |
Output is correct |
23 |
Correct |
9 ms |
3976 KB |
Output is correct |
24 |
Correct |
6 ms |
4004 KB |
Output is correct |
25 |
Correct |
2 ms |
2644 KB |
Output is correct |
26 |
Correct |
1 ms |
2644 KB |
Output is correct |
27 |
Correct |
9 ms |
4480 KB |
Output is correct |
28 |
Correct |
6 ms |
4052 KB |
Output is correct |
29 |
Correct |
6 ms |
3960 KB |
Output is correct |
30 |
Correct |
6 ms |
4052 KB |
Output is correct |
31 |
Correct |
2 ms |
2644 KB |
Output is correct |
32 |
Correct |
2 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
2644 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
23052 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
82 ms |
22736 KB |
Output is correct |
4 |
Correct |
91 ms |
22224 KB |
Output is correct |
5 |
Correct |
138 ms |
23112 KB |
Output is correct |
6 |
Correct |
118 ms |
23244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
18740 KB |
Output is correct |
2 |
Correct |
91 ms |
15392 KB |
Output is correct |
3 |
Correct |
93 ms |
15016 KB |
Output is correct |
4 |
Correct |
98 ms |
15008 KB |
Output is correct |
5 |
Correct |
106 ms |
15012 KB |
Output is correct |
6 |
Correct |
71 ms |
18892 KB |
Output is correct |
7 |
Correct |
75 ms |
18760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
18740 KB |
Output is correct |
2 |
Correct |
91 ms |
15392 KB |
Output is correct |
3 |
Correct |
93 ms |
15016 KB |
Output is correct |
4 |
Correct |
98 ms |
15008 KB |
Output is correct |
5 |
Correct |
106 ms |
15012 KB |
Output is correct |
6 |
Correct |
71 ms |
18892 KB |
Output is correct |
7 |
Correct |
75 ms |
18760 KB |
Output is correct |
8 |
Correct |
85 ms |
18928 KB |
Output is correct |
9 |
Correct |
90 ms |
20708 KB |
Output is correct |
10 |
Correct |
104 ms |
25056 KB |
Output is correct |
11 |
Correct |
96 ms |
24908 KB |
Output is correct |
12 |
Correct |
73 ms |
16488 KB |
Output is correct |
13 |
Correct |
65 ms |
16500 KB |
Output is correct |
14 |
Correct |
87 ms |
16716 KB |
Output is correct |
15 |
Correct |
128 ms |
16728 KB |
Output is correct |
16 |
Correct |
113 ms |
16788 KB |
Output is correct |
17 |
Correct |
84 ms |
16800 KB |
Output is correct |
18 |
Correct |
87 ms |
16812 KB |
Output is correct |
19 |
Correct |
97 ms |
17104 KB |
Output is correct |
20 |
Correct |
71 ms |
21004 KB |
Output is correct |
21 |
Correct |
71 ms |
21052 KB |
Output is correct |
22 |
Correct |
69 ms |
20940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
7 ms |
3924 KB |
Output is correct |
3 |
Correct |
6 ms |
3924 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
4492 KB |
Output is correct |
7 |
Correct |
6 ms |
4096 KB |
Output is correct |
8 |
Correct |
5 ms |
3956 KB |
Output is correct |
9 |
Correct |
8 ms |
4076 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
3 ms |
2676 KB |
Output is correct |
14 |
Correct |
2 ms |
2680 KB |
Output is correct |
15 |
Correct |
35 ms |
4388 KB |
Output is correct |
16 |
Correct |
28 ms |
4352 KB |
Output is correct |
17 |
Correct |
31 ms |
4400 KB |
Output is correct |
18 |
Correct |
6 ms |
4436 KB |
Output is correct |
19 |
Correct |
6 ms |
4108 KB |
Output is correct |
20 |
Correct |
27 ms |
4532 KB |
Output is correct |
21 |
Correct |
31 ms |
4520 KB |
Output is correct |
22 |
Correct |
2 ms |
2644 KB |
Output is correct |
23 |
Correct |
9 ms |
3976 KB |
Output is correct |
24 |
Correct |
6 ms |
4004 KB |
Output is correct |
25 |
Correct |
2 ms |
2644 KB |
Output is correct |
26 |
Correct |
1 ms |
2644 KB |
Output is correct |
27 |
Correct |
9 ms |
4480 KB |
Output is correct |
28 |
Correct |
6 ms |
4052 KB |
Output is correct |
29 |
Correct |
6 ms |
3960 KB |
Output is correct |
30 |
Correct |
6 ms |
4052 KB |
Output is correct |
31 |
Correct |
2 ms |
2644 KB |
Output is correct |
32 |
Correct |
2 ms |
2644 KB |
Output is correct |
33 |
Correct |
2 ms |
2644 KB |
Output is correct |
34 |
Correct |
2 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
36 |
Correct |
101 ms |
23052 KB |
Output is correct |
37 |
Correct |
2 ms |
2644 KB |
Output is correct |
38 |
Correct |
82 ms |
22736 KB |
Output is correct |
39 |
Correct |
91 ms |
22224 KB |
Output is correct |
40 |
Correct |
138 ms |
23112 KB |
Output is correct |
41 |
Correct |
118 ms |
23244 KB |
Output is correct |
42 |
Correct |
76 ms |
18740 KB |
Output is correct |
43 |
Correct |
91 ms |
15392 KB |
Output is correct |
44 |
Correct |
93 ms |
15016 KB |
Output is correct |
45 |
Correct |
98 ms |
15008 KB |
Output is correct |
46 |
Correct |
106 ms |
15012 KB |
Output is correct |
47 |
Correct |
71 ms |
18892 KB |
Output is correct |
48 |
Correct |
75 ms |
18760 KB |
Output is correct |
49 |
Correct |
85 ms |
18928 KB |
Output is correct |
50 |
Correct |
90 ms |
20708 KB |
Output is correct |
51 |
Correct |
104 ms |
25056 KB |
Output is correct |
52 |
Correct |
96 ms |
24908 KB |
Output is correct |
53 |
Correct |
73 ms |
16488 KB |
Output is correct |
54 |
Correct |
65 ms |
16500 KB |
Output is correct |
55 |
Correct |
87 ms |
16716 KB |
Output is correct |
56 |
Correct |
128 ms |
16728 KB |
Output is correct |
57 |
Correct |
113 ms |
16788 KB |
Output is correct |
58 |
Correct |
84 ms |
16800 KB |
Output is correct |
59 |
Correct |
87 ms |
16812 KB |
Output is correct |
60 |
Correct |
97 ms |
17104 KB |
Output is correct |
61 |
Correct |
71 ms |
21004 KB |
Output is correct |
62 |
Correct |
71 ms |
21052 KB |
Output is correct |
63 |
Correct |
69 ms |
20940 KB |
Output is correct |
64 |
Correct |
72 ms |
20924 KB |
Output is correct |
65 |
Correct |
87 ms |
16708 KB |
Output is correct |
66 |
Correct |
117 ms |
16660 KB |
Output is correct |
67 |
Correct |
86 ms |
16612 KB |
Output is correct |
68 |
Correct |
61 ms |
16616 KB |
Output is correct |
69 |
Correct |
61 ms |
16500 KB |
Output is correct |
70 |
Correct |
73 ms |
21104 KB |
Output is correct |
71 |
Correct |
105 ms |
20572 KB |
Output is correct |
72 |
Correct |
2 ms |
2676 KB |
Output is correct |
73 |
Correct |
5 ms |
3924 KB |
Output is correct |
74 |
Correct |
6 ms |
4052 KB |
Output is correct |
75 |
Correct |
2 ms |
2644 KB |
Output is correct |
76 |
Correct |
2 ms |
2680 KB |
Output is correct |
77 |
Correct |
6 ms |
4488 KB |
Output is correct |
78 |
Correct |
6 ms |
4052 KB |
Output is correct |
79 |
Correct |
6 ms |
4028 KB |
Output is correct |
80 |
Correct |
5 ms |
4052 KB |
Output is correct |
81 |
Correct |
2 ms |
2644 KB |
Output is correct |
82 |
Correct |
3 ms |
2680 KB |
Output is correct |
83 |
Correct |
2 ms |
2680 KB |
Output is correct |
84 |
Correct |
2 ms |
2680 KB |
Output is correct |
85 |
Correct |
2 ms |
2644 KB |
Output is correct |
86 |
Correct |
28 ms |
4376 KB |
Output is correct |
87 |
Correct |
34 ms |
4400 KB |
Output is correct |
88 |
Correct |
30 ms |
4400 KB |
Output is correct |
89 |
Correct |
7 ms |
4484 KB |
Output is correct |
90 |
Correct |
7 ms |
4052 KB |
Output is correct |
91 |
Correct |
24 ms |
4536 KB |
Output is correct |
92 |
Correct |
27 ms |
4436 KB |
Output is correct |
93 |
Correct |
1 ms |
2644 KB |
Output is correct |
94 |
Correct |
91 ms |
24932 KB |
Output is correct |
95 |
Correct |
79 ms |
24548 KB |
Output is correct |
96 |
Correct |
91 ms |
23996 KB |
Output is correct |
97 |
Correct |
107 ms |
24900 KB |
Output is correct |
98 |
Correct |
93 ms |
25284 KB |
Output is correct |
99 |
Correct |
108 ms |
16852 KB |
Output is correct |
100 |
Correct |
85 ms |
16856 KB |
Output is correct |
101 |
Correct |
79 ms |
16784 KB |
Output is correct |
102 |
Correct |
88 ms |
17244 KB |
Output is correct |
103 |
Correct |
67 ms |
20644 KB |
Output is correct |
104 |
Correct |
88 ms |
21024 KB |
Output is correct |
105 |
Correct |
68 ms |
20664 KB |
Output is correct |
106 |
Correct |
110 ms |
20844 KB |
Output is correct |
107 |
Correct |
82 ms |
20704 KB |
Output is correct |
108 |
Correct |
90 ms |
24976 KB |
Output is correct |
109 |
Correct |
97 ms |
25040 KB |
Output is correct |
110 |
Correct |
72 ms |
16592 KB |
Output is correct |
111 |
Correct |
66 ms |
16596 KB |
Output is correct |
112 |
Correct |
84 ms |
16716 KB |
Output is correct |
113 |
Correct |
91 ms |
16660 KB |
Output is correct |