# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
162409 |
2019-11-08T07:25:14 Z |
MvC |
Railway (BOI17_railway) |
C++11 |
|
72 ms |
14712 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,id[nmax],vl[nmax],cur;
vector<pair<int,int> >a[nmax];
bitset<nmax>on;
void dfs(int x,int p)
{
in[x]=++tin;
id[tin]=x;
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)
{
id[++cur]=x;
in[x]=cur;
ed[cur]=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);
}
}
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);
for(i=1;i<n;i++)
{
if((int)a[i].size()==1)
{
x=i;
break;
}
}
sol(x,x,0);
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,in[y]);
}
if(x)
{
vl[id[mn]]++;
vl[id[mx]]--;
}
}
for(i=1;i<n;i++)
{
vl[id[i]]+=vl[id[i-1]];
if(vl[id[i]]>=k)rs++;
}
cout<<rs<<endl;
for(i=1;i<n;i++)
{
if(vl[id[i]]>=k)cout<<ed[id[i+1]]<<" ";
}
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 |
Incorrect |
5 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
13020 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
68 ms |
14200 KB |
Output is correct |
4 |
Correct |
71 ms |
13956 KB |
Output is correct |
5 |
Correct |
64 ms |
14328 KB |
Output is correct |
6 |
Correct |
72 ms |
14712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
70 ms |
10616 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
70 ms |
10616 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |