Submission #544485

#	Time	Username	Problem	Language	Result	Execution time	Memory
544485		somo	Railway (BOI17_railway)	C++14	0 / 100	137 ms	37672 KiB

railway

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll>
#define F first
#define S second
#define double long double
#define all(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;

const int MOD = 1e9 + 7;
const int  N=5e5 + 7 ;
const ll INF= 1e18+10;

struct trp{ll F,S,T;};

ll po(ll x,ll y)
{
    ll ans = 1;
    while(y){
        if( y & 1 ) ans *=x;
        y /= 2;
        x *=x;
        x %= MOD;
        ans %= MOD;
    }
    return ans;
}

ll ans[N];
ll edj[N]; // number of edje between i and its father
ll par[N];
bool is[N];
ll n ,m , k;
vector<pii>v[N];
vector<ll>from_child[N];

void dfs(ll x,ll p)
{
    par[x] = p;
    for(auto i : v[x]){
        if(i.F == p){
            edj[x] = i.S;
            continue;
        }
        dfs(i.F , x);
    }
}

void solve()
{
    cin >> n >> m >> k;
    for(ll i= 1; i < n ; i ++){
        ll x,y;
        cin >> x >> y;
        v[x].pb({y,i});
        v[y].pb({x,i});
    }
    dfs(1,1);
    vector<ll>vec;
    for(ll i= 1; i <= m ; i ++){
        ll s;
        cin >> s;
        while(s -- ){
            ll x;
            cin >> x;
            vec.pb(x);
        }
        for(auto i : vec){
            is[i] = 1;
            for(auto j : from_child[i]){
                ans[j] ++ ;
            }
            if(i != 1){
                if(is[par[i]]) ans[edj[i]] ++;
                else from_child[par[i]].pb(edj[i]);
            }
        }
        for(auto i : vec) is[i] = 0 , from_child[i].clear();;
        vec.clear();
    }
    for(ll i= 1; i < n ; i ++){
        if(ans[i] >= k) vec.pb(i);
    }
    cout << vec.size() << endl;
    for(auto i : vec) cout << i << ' ' ;
}

int main(){
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen(".in" , "r" , stdin);freopen(".out" , "w" , stdout);
	int t = 1;
    //cin >> t;
	while(t--) {solve() ; }
}

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