Submission #723651

#	Time	Username	Problem	Language	Result	Execution time	Memory
723651		anusha777	Railway (BOI17_railway)	C++14	23 / 100	1083 ms	19220 KiB

railway

#include <bits/stdc++.h>
#define fast 			ios::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL)
#define sz(x)			(int)((x).size())
#define pb				push_back
#define vi				vector<int>
#define vb				vector<bool>
#define vvb				vector<vb>
#define pi				pair<int,int>
#define vpi				vector<pi>
#define vvi				vector<vi>
#define vc				vector<char>
#define all(x)			x.begin(), x.end()
#define rall(x)			x.rbegin(), x.rend()
#define pbb()			pop_back()
#define f				first
#define s				second
#define ll				long long
#define int				long long
#define ull				unsigned long long
#define line               cout<<"_____________________________"<<endl;
#define forr(i, a, b)      for(int i=a; i<b; i++)
const int N=1e5+1, mod=1e9+7, inf=1e18+1;
using namespace std;
vpi out[N];
int f[N]={0};
int n, m,k;
bool take[N];
vpi a;
void init()
{
    forr(i, 0, N) take[i]=0;
}

void dfs(int u, int p)
{
    if(take[u]) for(int i=sz(a)-1; i>=0 and a[i].s==0; i--)
    {
        f[a[i].first]++;
        a[i].second=1;
    }
    for(pi v: out[u]) if(p!=v.f)
        {
            a.pb({v.s, 0});
            dfs(v.f, u);
        }
    a.pbb();
}
void task()
{
    cin>>n>>m>>k;
    forr(i, 1, n)
    {
        int u, v;
        cin>>u>>v;
        out[u].pb({v,i});
        out[v].pb({u,i});
    }
    while (m--)
    {
        int s;
        cin>>s;
        init();
        int start=-1;
        while(s--)
        {
            cin>>start;
            take[start]=1;
        }
        dfs(start, 0);
        a.clear();
    }
    vi b;
    for(int i=1; i<n; i++) if(f[i]>=k) b.pb(i);
    cout<<sz(b)<<endl;
    for(int t: b) cout<<t<<' ';
    cout<<endl;
}
signed main()
{
    fast;
    int t;
    t=1;
    //cin>>t;
    while(t--)task();
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25