# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
932090 |
2024-02-23T00:59:25 Z |
irmuun |
Railway (BOI17_railway) |
C++17 |
|
1000 ms |
21308 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
vector<int>adj[n+5];
vector<pair<int,int>>edge;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
edge.pb({u,v});
adj[u].pb(v);
adj[v].pb(u);
}
int s[m+5];
vector<int>need[m+5];
for(int i=1;i<=m;i++){
cin>>s[i];
need[i].resize(s[i]);
for(int j=0;j<s[i];j++){
cin>>need[i][j];
}
}
vector<int>par(n+5);
vector<int>f(n+5),e(n+5);
int cur=0;
function <void(int,int)> dfs=[&](int x,int p){
f[x]=cur++;
par[x]=p;
for(auto y:adj[x]){
if(y!=p){
dfs(y,x);
}
}
e[x]=cur++;
};
vector<int>cnt(n+5,0),a(n+5,0);
function <void(int,int)> dfs1=[&](int x,int p){
cnt[x]=a[x];
for(auto y:adj[x]){
if(y!=p){
dfs1(y,x);
cnt[x]+=cnt[y];
}
}
};
dfs(1,0);
cur=0;
vector<int>ans,choose(n+5,0);
for(int j=1;j<=m;j++){
fill(all(a),0);
for(auto i:need[j]){
a[i]=1;
}
dfs1(1,0);
for(int i=0;i<n;i++){
auto [x,y]=edge[i];
if(par[y]==x) swap(x,y);
if(0<cnt[x]&&cnt[x]<s[j]){
choose[i+1]++;
}
}
}
for(int i=1;i<n;i++){
if(choose[i]>=k){
ans.pb(i);
}
}
cout<<ans.size()<<"\n";
for(auto i:ans){
cout<<i<<' ';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
500 KB |
Output is correct |
2 |
Correct |
48 ms |
1280 KB |
Output is correct |
3 |
Correct |
48 ms |
1116 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
84 ms |
1800 KB |
Output is correct |
7 |
Correct |
24 ms |
1368 KB |
Output is correct |
8 |
Correct |
94 ms |
1372 KB |
Output is correct |
9 |
Correct |
109 ms |
1372 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
500 KB |
Output is correct |
2 |
Correct |
48 ms |
1280 KB |
Output is correct |
3 |
Correct |
48 ms |
1116 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
84 ms |
1800 KB |
Output is correct |
7 |
Correct |
24 ms |
1368 KB |
Output is correct |
8 |
Correct |
94 ms |
1372 KB |
Output is correct |
9 |
Correct |
109 ms |
1372 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
343 ms |
1628 KB |
Output is correct |
16 |
Correct |
352 ms |
2192 KB |
Output is correct |
17 |
Correct |
349 ms |
2152 KB |
Output is correct |
18 |
Correct |
348 ms |
2020 KB |
Output is correct |
19 |
Correct |
210 ms |
1368 KB |
Output is correct |
20 |
Correct |
93 ms |
2388 KB |
Output is correct |
21 |
Correct |
102 ms |
2276 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
52 ms |
1372 KB |
Output is correct |
24 |
Correct |
51 ms |
1372 KB |
Output is correct |
25 |
Correct |
0 ms |
344 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
82 ms |
1900 KB |
Output is correct |
28 |
Correct |
24 ms |
1372 KB |
Output is correct |
29 |
Correct |
92 ms |
1372 KB |
Output is correct |
30 |
Correct |
104 ms |
1368 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1083 ms |
21308 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1047 ms |
16580 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1047 ms |
16580 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
500 KB |
Output is correct |
2 |
Correct |
48 ms |
1280 KB |
Output is correct |
3 |
Correct |
48 ms |
1116 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
84 ms |
1800 KB |
Output is correct |
7 |
Correct |
24 ms |
1368 KB |
Output is correct |
8 |
Correct |
94 ms |
1372 KB |
Output is correct |
9 |
Correct |
109 ms |
1372 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
343 ms |
1628 KB |
Output is correct |
16 |
Correct |
352 ms |
2192 KB |
Output is correct |
17 |
Correct |
349 ms |
2152 KB |
Output is correct |
18 |
Correct |
348 ms |
2020 KB |
Output is correct |
19 |
Correct |
210 ms |
1368 KB |
Output is correct |
20 |
Correct |
93 ms |
2388 KB |
Output is correct |
21 |
Correct |
102 ms |
2276 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
52 ms |
1372 KB |
Output is correct |
24 |
Correct |
51 ms |
1372 KB |
Output is correct |
25 |
Correct |
0 ms |
344 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
82 ms |
1900 KB |
Output is correct |
28 |
Correct |
24 ms |
1372 KB |
Output is correct |
29 |
Correct |
92 ms |
1372 KB |
Output is correct |
30 |
Correct |
104 ms |
1368 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Execution timed out |
1083 ms |
21308 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |