# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
826807 |
2023-08-16T04:30:18 Z |
8pete8 |
Railway (BOI17_railway) |
C++14 |
|
111 ms |
47684 KB |
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<cmath>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
//#define int long long
#define mod 1000000007
#define int long long
const int mxn=1e5,lg=20,inf=1e18;
vector<pii>e,adj[mxn+10];
int h[mxn+10],up[mxn+10][lg+10],add[mxn+10],ans[mxn+10],st[mxn+10];
bitset<mxn+10>vis;
int t=0;
void solve(int cur,int p){
st[cur]=t++;
for(auto i:adj[cur]){
if(i.f==p)continue;
up[i.f][0]=cur;
h[i.f]=h[cur]+1;
solve(i.f,cur);
}
}
int push(int cur,int p){
int cnt=add[cur],g;
for(auto i:adj[cur]){
if(i.f==p)continue;
g=push(i.f,cur);
ans[i.s]+=g;
cnt+=g;
}
return cnt;
}
bool cmp(int a,int b){return st[a]>st[b];}
int lca(int a,int b){
if(h[a]<h[b])swap(a,b);
int k=h[a]-h[b];
for(int i=0;i<=lg;i++)if(k&(1<<i))a=up[a][i];
if(a==b)return a;
for(int i=lg;i>=0;i--)if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i];
return up[a][0];
}
int32_t main(){
fastio
int n,m,k;cin>>n>>m>>k;
for(int i=0;i<n-1;i++){
int u,v;cin>>u>>v;
adj[u].pb({v,i});
adj[v].pb({u,i});
e.pb({u,v});
}
solve(1,-1);
for(int i=1;i<=lg;i++)for(int j=1;j<=n;j++)up[j][i]=up[up[j][i-1]][i-1];
while(m--){
int a;cin>>a;
vector<int>an(a);
vis.reset();
for(int i=0;i<a;i++)cin>>an[i];
sort(an.begin(),an.end(),cmp);
int node;
for(int i=0;i<a;i++){
node=lca(an[i],an[(i+1)%a]);
add[node]-=2;
add[an[i]]++;
add[an[(i+1)%a]]++;
}
}
push(1,-1);
vector<int>v;
for(int i=0;i<n-1;i++)if(ans[i]>=2*k)v.pb(i+1);
cout<<v.size()<<'\n';
for(auto i:v)cout<<i<<" ";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
5 ms |
5948 KB |
Output is correct |
3 |
Correct |
6 ms |
6096 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
6664 KB |
Output is correct |
7 |
Correct |
5 ms |
6224 KB |
Output is correct |
8 |
Correct |
5 ms |
6096 KB |
Output is correct |
9 |
Correct |
5 ms |
6148 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
1 ms |
2680 KB |
Output is correct |
14 |
Correct |
2 ms |
2688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
5 ms |
5948 KB |
Output is correct |
3 |
Correct |
6 ms |
6096 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
6664 KB |
Output is correct |
7 |
Correct |
5 ms |
6224 KB |
Output is correct |
8 |
Correct |
5 ms |
6096 KB |
Output is correct |
9 |
Correct |
5 ms |
6148 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
1 ms |
2680 KB |
Output is correct |
14 |
Correct |
2 ms |
2688 KB |
Output is correct |
15 |
Correct |
19 ms |
6436 KB |
Output is correct |
16 |
Correct |
20 ms |
6524 KB |
Output is correct |
17 |
Correct |
21 ms |
6564 KB |
Output is correct |
18 |
Correct |
6 ms |
6608 KB |
Output is correct |
19 |
Correct |
6 ms |
6148 KB |
Output is correct |
20 |
Correct |
27 ms |
6608 KB |
Output is correct |
21 |
Correct |
30 ms |
6564 KB |
Output is correct |
22 |
Correct |
1 ms |
2644 KB |
Output is correct |
23 |
Correct |
5 ms |
6096 KB |
Output is correct |
24 |
Correct |
7 ms |
6144 KB |
Output is correct |
25 |
Correct |
1 ms |
2688 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
8 ms |
6608 KB |
Output is correct |
28 |
Correct |
5 ms |
6224 KB |
Output is correct |
29 |
Correct |
7 ms |
6096 KB |
Output is correct |
30 |
Correct |
5 ms |
6096 KB |
Output is correct |
31 |
Correct |
2 ms |
2680 KB |
Output is correct |
32 |
Correct |
2 ms |
2664 KB |
Output is correct |
33 |
Correct |
1 ms |
2644 KB |
Output is correct |
34 |
Correct |
1 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
45392 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
103 ms |
46328 KB |
Output is correct |
4 |
Correct |
89 ms |
45124 KB |
Output is correct |
5 |
Correct |
99 ms |
47296 KB |
Output is correct |
6 |
Correct |
78 ms |
47684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
39444 KB |
Output is correct |
2 |
Correct |
101 ms |
36240 KB |
Output is correct |
3 |
Correct |
100 ms |
35924 KB |
Output is correct |
4 |
Correct |
87 ms |
35920 KB |
Output is correct |
5 |
Correct |
84 ms |
35976 KB |
Output is correct |
6 |
Correct |
76 ms |
39676 KB |
Output is correct |
7 |
Correct |
73 ms |
39608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
39444 KB |
Output is correct |
2 |
Correct |
101 ms |
36240 KB |
Output is correct |
3 |
Correct |
100 ms |
35924 KB |
Output is correct |
4 |
Correct |
87 ms |
35920 KB |
Output is correct |
5 |
Correct |
84 ms |
35976 KB |
Output is correct |
6 |
Correct |
76 ms |
39676 KB |
Output is correct |
7 |
Correct |
73 ms |
39608 KB |
Output is correct |
8 |
Correct |
84 ms |
40072 KB |
Output is correct |
9 |
Correct |
90 ms |
41888 KB |
Output is correct |
10 |
Correct |
78 ms |
47432 KB |
Output is correct |
11 |
Correct |
111 ms |
47328 KB |
Output is correct |
12 |
Correct |
70 ms |
36936 KB |
Output is correct |
13 |
Correct |
70 ms |
36928 KB |
Output is correct |
14 |
Correct |
79 ms |
37640 KB |
Output is correct |
15 |
Correct |
81 ms |
37616 KB |
Output is correct |
16 |
Correct |
88 ms |
37688 KB |
Output is correct |
17 |
Correct |
85 ms |
37772 KB |
Output is correct |
18 |
Correct |
88 ms |
37748 KB |
Output is correct |
19 |
Correct |
79 ms |
38072 KB |
Output is correct |
20 |
Correct |
78 ms |
41788 KB |
Output is correct |
21 |
Correct |
76 ms |
42252 KB |
Output is correct |
22 |
Correct |
75 ms |
41856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
5 ms |
5948 KB |
Output is correct |
3 |
Correct |
6 ms |
6096 KB |
Output is correct |
4 |
Correct |
1 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
6664 KB |
Output is correct |
7 |
Correct |
5 ms |
6224 KB |
Output is correct |
8 |
Correct |
5 ms |
6096 KB |
Output is correct |
9 |
Correct |
5 ms |
6148 KB |
Output is correct |
10 |
Correct |
1 ms |
2644 KB |
Output is correct |
11 |
Correct |
1 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
1 ms |
2680 KB |
Output is correct |
14 |
Correct |
2 ms |
2688 KB |
Output is correct |
15 |
Correct |
19 ms |
6436 KB |
Output is correct |
16 |
Correct |
20 ms |
6524 KB |
Output is correct |
17 |
Correct |
21 ms |
6564 KB |
Output is correct |
18 |
Correct |
6 ms |
6608 KB |
Output is correct |
19 |
Correct |
6 ms |
6148 KB |
Output is correct |
20 |
Correct |
27 ms |
6608 KB |
Output is correct |
21 |
Correct |
30 ms |
6564 KB |
Output is correct |
22 |
Correct |
1 ms |
2644 KB |
Output is correct |
23 |
Correct |
5 ms |
6096 KB |
Output is correct |
24 |
Correct |
7 ms |
6144 KB |
Output is correct |
25 |
Correct |
1 ms |
2688 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
8 ms |
6608 KB |
Output is correct |
28 |
Correct |
5 ms |
6224 KB |
Output is correct |
29 |
Correct |
7 ms |
6096 KB |
Output is correct |
30 |
Correct |
5 ms |
6096 KB |
Output is correct |
31 |
Correct |
2 ms |
2680 KB |
Output is correct |
32 |
Correct |
2 ms |
2664 KB |
Output is correct |
33 |
Correct |
1 ms |
2644 KB |
Output is correct |
34 |
Correct |
1 ms |
2644 KB |
Output is correct |
35 |
Correct |
2 ms |
2644 KB |
Output is correct |
36 |
Correct |
91 ms |
45392 KB |
Output is correct |
37 |
Correct |
1 ms |
2644 KB |
Output is correct |
38 |
Correct |
103 ms |
46328 KB |
Output is correct |
39 |
Correct |
89 ms |
45124 KB |
Output is correct |
40 |
Correct |
99 ms |
47296 KB |
Output is correct |
41 |
Correct |
78 ms |
47684 KB |
Output is correct |
42 |
Correct |
87 ms |
39444 KB |
Output is correct |
43 |
Correct |
101 ms |
36240 KB |
Output is correct |
44 |
Correct |
100 ms |
35924 KB |
Output is correct |
45 |
Correct |
87 ms |
35920 KB |
Output is correct |
46 |
Correct |
84 ms |
35976 KB |
Output is correct |
47 |
Correct |
76 ms |
39676 KB |
Output is correct |
48 |
Correct |
73 ms |
39608 KB |
Output is correct |
49 |
Correct |
84 ms |
40072 KB |
Output is correct |
50 |
Correct |
90 ms |
41888 KB |
Output is correct |
51 |
Correct |
78 ms |
47432 KB |
Output is correct |
52 |
Correct |
111 ms |
47328 KB |
Output is correct |
53 |
Correct |
70 ms |
36936 KB |
Output is correct |
54 |
Correct |
70 ms |
36928 KB |
Output is correct |
55 |
Correct |
79 ms |
37640 KB |
Output is correct |
56 |
Correct |
81 ms |
37616 KB |
Output is correct |
57 |
Correct |
88 ms |
37688 KB |
Output is correct |
58 |
Correct |
85 ms |
37772 KB |
Output is correct |
59 |
Correct |
88 ms |
37748 KB |
Output is correct |
60 |
Correct |
79 ms |
38072 KB |
Output is correct |
61 |
Correct |
78 ms |
41788 KB |
Output is correct |
62 |
Correct |
76 ms |
42252 KB |
Output is correct |
63 |
Correct |
75 ms |
41856 KB |
Output is correct |
64 |
Correct |
82 ms |
42112 KB |
Output is correct |
65 |
Correct |
100 ms |
37768 KB |
Output is correct |
66 |
Correct |
104 ms |
37732 KB |
Output is correct |
67 |
Correct |
86 ms |
37696 KB |
Output is correct |
68 |
Correct |
58 ms |
36808 KB |
Output is correct |
69 |
Correct |
59 ms |
36860 KB |
Output is correct |
70 |
Correct |
86 ms |
42760 KB |
Output is correct |
71 |
Correct |
85 ms |
41588 KB |
Output is correct |
72 |
Correct |
1 ms |
2684 KB |
Output is correct |
73 |
Correct |
5 ms |
6152 KB |
Output is correct |
74 |
Correct |
5 ms |
6096 KB |
Output is correct |
75 |
Correct |
1 ms |
2644 KB |
Output is correct |
76 |
Correct |
1 ms |
2644 KB |
Output is correct |
77 |
Correct |
6 ms |
6608 KB |
Output is correct |
78 |
Correct |
5 ms |
6144 KB |
Output is correct |
79 |
Correct |
6 ms |
6096 KB |
Output is correct |
80 |
Correct |
5 ms |
6096 KB |
Output is correct |
81 |
Correct |
1 ms |
2644 KB |
Output is correct |
82 |
Correct |
1 ms |
2644 KB |
Output is correct |
83 |
Correct |
1 ms |
2684 KB |
Output is correct |
84 |
Correct |
2 ms |
2680 KB |
Output is correct |
85 |
Correct |
1 ms |
2644 KB |
Output is correct |
86 |
Correct |
19 ms |
6484 KB |
Output is correct |
87 |
Correct |
19 ms |
6576 KB |
Output is correct |
88 |
Correct |
20 ms |
6580 KB |
Output is correct |
89 |
Correct |
6 ms |
6608 KB |
Output is correct |
90 |
Correct |
6 ms |
6224 KB |
Output is correct |
91 |
Correct |
22 ms |
6600 KB |
Output is correct |
92 |
Correct |
24 ms |
6520 KB |
Output is correct |
93 |
Correct |
1 ms |
2644 KB |
Output is correct |
94 |
Correct |
95 ms |
47208 KB |
Output is correct |
95 |
Correct |
92 ms |
46280 KB |
Output is correct |
96 |
Correct |
87 ms |
45116 KB |
Output is correct |
97 |
Correct |
101 ms |
47292 KB |
Output is correct |
98 |
Correct |
89 ms |
47684 KB |
Output is correct |
99 |
Correct |
84 ms |
37688 KB |
Output is correct |
100 |
Correct |
81 ms |
37788 KB |
Output is correct |
101 |
Correct |
85 ms |
37748 KB |
Output is correct |
102 |
Correct |
78 ms |
38080 KB |
Output is correct |
103 |
Correct |
73 ms |
41436 KB |
Output is correct |
104 |
Correct |
86 ms |
42228 KB |
Output is correct |
105 |
Correct |
74 ms |
41364 KB |
Output is correct |
106 |
Correct |
82 ms |
42124 KB |
Output is correct |
107 |
Correct |
91 ms |
41864 KB |
Output is correct |
108 |
Correct |
85 ms |
47368 KB |
Output is correct |
109 |
Correct |
87 ms |
47432 KB |
Output is correct |
110 |
Correct |
69 ms |
36976 KB |
Output is correct |
111 |
Correct |
68 ms |
37036 KB |
Output is correct |
112 |
Correct |
76 ms |
37688 KB |
Output is correct |
113 |
Correct |
74 ms |
37672 KB |
Output is correct |