# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
162408 |
2019-11-08T07:14:01 Z |
MvC |
Railway (BOI17_railway) |
C++11 |
|
1000 ms |
24108 KB |
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,m,k,i,x,y,in[nmax],out[nmax],tin,up[nmax][20],mn,mx,ed[nmax],rs;
vector<pair<int,int> >a[nmax];
bitset<nmax>on;
void dfs(int x,int p)
{
in[x]=++tin;
up[x][0]=p;
for(int i=1;i<19;i++)up[x][i]=up[up[x][i-1]][i-1];
for(int i=0;i<(int)a[x].size();i++)
{
int y=a[x][i].fr;
if(y==p)continue;
dfs(y,x);
}
out[x]=++tin;
}
void sol(int x,int p,int e)
{
for(int i=0;i<(int)a[x].size();i++)
{
int y=a[x][i].fr;
if(y==p)continue;
sol(y,x,a[x][i].sc);
if(on[y])on[x]=1;
}
if(on[x] && (mn<in[x] || mx>out[x]))ed[e]++;
}
int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(i=1;i<n;i++)
{
cin>>x>>y;
a[x].pb(mkp(y,i));
a[y].pb(mkp(x,i));
}
dfs(1,1);
while(m--)
{
cin>>x;
mn=inf,mx=0;
for(i=1;i<=x;i++)
{
cin>>y;
on[y]=1;
mn=min(mn,in[y]);
mx=max(mx,out[y]);
}
if(x)
{
sol(1,1,0);
on.reset();
}
}
for(i=1;i<n;i++)if(ed[i]>=k)rs++;
cout<<rs<<endl;
for(i=1;i<n;i++)if(ed[i]>=k)cout<<i<<" ";
cout<<endl;
return 0;
}
Compilation message
railway.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("O3")
railway.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("unroll-loops")
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2680 KB |
Output is correct |
2 |
Correct |
80 ms |
4088 KB |
Output is correct |
3 |
Correct |
79 ms |
4216 KB |
Output is correct |
4 |
Correct |
5 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2680 KB |
Output is correct |
6 |
Correct |
111 ms |
4472 KB |
Output is correct |
7 |
Correct |
44 ms |
4256 KB |
Output is correct |
8 |
Correct |
131 ms |
4088 KB |
Output is correct |
9 |
Correct |
167 ms |
4216 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
5 ms |
2680 KB |
Output is correct |
12 |
Correct |
4 ms |
2680 KB |
Output is correct |
13 |
Correct |
7 ms |
2808 KB |
Output is correct |
14 |
Correct |
5 ms |
2680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2680 KB |
Output is correct |
2 |
Correct |
80 ms |
4088 KB |
Output is correct |
3 |
Correct |
79 ms |
4216 KB |
Output is correct |
4 |
Correct |
5 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2680 KB |
Output is correct |
6 |
Correct |
111 ms |
4472 KB |
Output is correct |
7 |
Correct |
44 ms |
4256 KB |
Output is correct |
8 |
Correct |
131 ms |
4088 KB |
Output is correct |
9 |
Correct |
167 ms |
4216 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
5 ms |
2680 KB |
Output is correct |
12 |
Correct |
4 ms |
2680 KB |
Output is correct |
13 |
Correct |
7 ms |
2808 KB |
Output is correct |
14 |
Correct |
5 ms |
2680 KB |
Output is correct |
15 |
Correct |
547 ms |
4444 KB |
Output is correct |
16 |
Correct |
547 ms |
4624 KB |
Output is correct |
17 |
Correct |
595 ms |
4600 KB |
Output is correct |
18 |
Correct |
790 ms |
4600 KB |
Output is correct |
19 |
Correct |
340 ms |
4224 KB |
Output is correct |
20 |
Correct |
118 ms |
4600 KB |
Output is correct |
21 |
Correct |
132 ms |
4600 KB |
Output is correct |
22 |
Correct |
4 ms |
2808 KB |
Output is correct |
23 |
Correct |
79 ms |
4140 KB |
Output is correct |
24 |
Correct |
78 ms |
4088 KB |
Output is correct |
25 |
Correct |
4 ms |
2808 KB |
Output is correct |
26 |
Correct |
4 ms |
2680 KB |
Output is correct |
27 |
Correct |
128 ms |
4580 KB |
Output is correct |
28 |
Correct |
43 ms |
4216 KB |
Output is correct |
29 |
Correct |
133 ms |
4216 KB |
Output is correct |
30 |
Correct |
173 ms |
4088 KB |
Output is correct |
31 |
Correct |
4 ms |
2680 KB |
Output is correct |
32 |
Correct |
5 ms |
2808 KB |
Output is correct |
33 |
Correct |
4 ms |
2808 KB |
Output is correct |
34 |
Correct |
5 ms |
2684 KB |
Output is correct |
35 |
Correct |
16 ms |
2684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1040 ms |
24108 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1083 ms |
20728 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1083 ms |
20728 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2680 KB |
Output is correct |
2 |
Correct |
80 ms |
4088 KB |
Output is correct |
3 |
Correct |
79 ms |
4216 KB |
Output is correct |
4 |
Correct |
5 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2680 KB |
Output is correct |
6 |
Correct |
111 ms |
4472 KB |
Output is correct |
7 |
Correct |
44 ms |
4256 KB |
Output is correct |
8 |
Correct |
131 ms |
4088 KB |
Output is correct |
9 |
Correct |
167 ms |
4216 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
5 ms |
2680 KB |
Output is correct |
12 |
Correct |
4 ms |
2680 KB |
Output is correct |
13 |
Correct |
7 ms |
2808 KB |
Output is correct |
14 |
Correct |
5 ms |
2680 KB |
Output is correct |
15 |
Correct |
547 ms |
4444 KB |
Output is correct |
16 |
Correct |
547 ms |
4624 KB |
Output is correct |
17 |
Correct |
595 ms |
4600 KB |
Output is correct |
18 |
Correct |
790 ms |
4600 KB |
Output is correct |
19 |
Correct |
340 ms |
4224 KB |
Output is correct |
20 |
Correct |
118 ms |
4600 KB |
Output is correct |
21 |
Correct |
132 ms |
4600 KB |
Output is correct |
22 |
Correct |
4 ms |
2808 KB |
Output is correct |
23 |
Correct |
79 ms |
4140 KB |
Output is correct |
24 |
Correct |
78 ms |
4088 KB |
Output is correct |
25 |
Correct |
4 ms |
2808 KB |
Output is correct |
26 |
Correct |
4 ms |
2680 KB |
Output is correct |
27 |
Correct |
128 ms |
4580 KB |
Output is correct |
28 |
Correct |
43 ms |
4216 KB |
Output is correct |
29 |
Correct |
133 ms |
4216 KB |
Output is correct |
30 |
Correct |
173 ms |
4088 KB |
Output is correct |
31 |
Correct |
4 ms |
2680 KB |
Output is correct |
32 |
Correct |
5 ms |
2808 KB |
Output is correct |
33 |
Correct |
4 ms |
2808 KB |
Output is correct |
34 |
Correct |
5 ms |
2684 KB |
Output is correct |
35 |
Correct |
16 ms |
2684 KB |
Output is correct |
36 |
Execution timed out |
1040 ms |
24108 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |