제출 #723705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723705		anusha777	Railway (BOI17_railway)	C++14	7 / 100	59 ms	18636 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}, h[N]={0};
vpi dp(N);
int n, m,k;
void dfs(int u, int p)
{
    h[u]=h[p]+1;
    for(pi v: out[u]) if(v.f!=p)
    {
        dp[h[u]+1].f=v.second;
        dfs(v.f, u);
    }
}
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});
    }
   forr(i, 1, n+1) if(sz(out[i])==1)
        {
            dfs(i, 0);
            break;
        }
    while (m--)
    {
        int s;
        cin>>s;
        int start=n+1, end=0;
        while(s--)
        {
            int t;
            cin>>t;
            start=min(start , h[t]);
            end=max(end , h[t]);
        }
        dp[start+1].s++;
        dp[end+1].s--;
    }
    forr(i, 1, n+1)
    {
        dp[i].s+= dp[i-1].s;
        f[dp[i].first]=dp[i].s;
    }
    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: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 7 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25