Submission #263140

#	Time	Username	Problem	Language	Result	Execution time	Memory
263140		Hehehe	Railway (BOI17_railway)	C++14	100 / 100	155 ms	41456 KiB

railway

#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<long double, long double>
#define sz(x) (int)((x).size())
//#define int long long

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 2e5 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

int n, m, k, dp[N][50], cnt[N], tin[N], tout[N], t;
pi e[N];
vector<int>v[N];

void dfs(int nod, int p){

    tin[nod] = ++t;
    dp[nod][0] = p;

    for(auto it : v[nod]){
        if(it == p)continue;
        dfs(it, nod);
    }

    tout[nod] = ++t;
}

void hug(){
    for(int i = 1; i <= 20; i++){
        for(int j = 1; j <= n; j++){
            dp[j][i] = dp[dp[j][i - 1]][i - 1];
        }
    }
}

bool is_ancestor(int p, int x){
    if(tin[p] <= tin[x] && tout[x] <= tout[p]) return 1;
    return 0;
}

int lca(int x, int y){
    if(is_ancestor(x,y))return x;
    if(is_ancestor(y,x))return y;
    for(int i = 20; i >= 0; i--){
        if(!is_ancestor(dp[x][i], y) && dp[x][i] != 0)x = dp[x][i];
    }
    return dp[x][0];
}

void dfs2(int nod, int p){
    for(auto it : v[nod]){
        if(it == p)continue;
        dfs2(it, nod);
        cnt[nod] += cnt[it];
    }
}

void solve(){

    cin >> n >> m >> k;

    for(int i = 1, x, y; i < n; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        e[i] = {x, y};
    }

    dfs(1, 0);

    hug();

    for(int i = 1, x; i <= m; i++){
        cin >> x;
        vector<int>V;

        for(int j = 1, y; j <= x; j++){
            cin >> y;
            V.push_back(y);
        }

        sort(all(V),[](int l, int r){
             return (tin[l] < tin[r]);
        });

        for(int j = 0; j < sz(V); j++){
            int x = V[j], y = V[(j + 1) % sz(V)];
            cnt[x]++;
            cnt[y]++;
            cnt[lca(x,y)] -= 2;
        }
    }

    dfs2(1, 0);

    vector<int>ans;
    for(int i = 1; i < n; i++){
        int a = e[i].ff, b = e[i].ss;
        if(tin[a] > tin[b])swap(a, b);
        if(cnt[b] >= 2*k)ans.push_back(i);
    }

    cout << sz(ans) << '\n';
    for(auto it : ans)cout << it << ' ';
}



int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //cout << setprecision(6) << fixed;

    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}

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