Submission #1096212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096212		Niosakaru	Railway (BOI17_railway)	C++17	100 / 100	102 ms	39068 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
#define ii pair <int,int>

const int N = 1e5 + 5 , Lg = 17;

int n , m , k , u , v , P , T , Roto , in[N] , d[N] , x[N] , dp[N] , p[N][Lg] , cnt[N];
vector <ii> adj[N];
vector <int> rt , qu[N];

void dfs(int u){
    in[u] = ++ T;
    for (int i = 1 ; i < Lg ; i ++) p[u][i] = p[p[u][i-1]][i-1];
    for (auto i : adj[u]) if (i.first != p[u][0])
    {
        p[i.first][0] = u , d[i.first] = d[u] + 1;
        dfs(i.first);
    }
}

int __lca(int u,int v){
    if (d[u] < d[v]) swap(u,v);
    for (int i = Lg - 1 ; i >= 0 ; i --) if (d[p[u][i]] >= d[v]) u = p[u][i];
    if (u == v) return u;
    for (int i = Lg - 1 ; i >= 0 ; i --) if (p[u][i] != p[v][i]) u = p[u][i] , v = p[v][i];
    return p[u][0];
}

bool cmp(int& a,int& b){
    return in[a] < in[b];
}

void calc(int u){
    for (int j = 0 ; j < (int)adj[u].size() ; j ++){
        int v = adj[u][j].first , i = adj[u][j].second;
        if (v == p[u][0]) continue;
        calc(v) , cnt[i] = dp[v] , dp[u] += dp[v];
    }
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> k;
    for (int i = 1 ; i < n ; i ++) cin >> u >> v , adj[u].push_back(mp(v,i)) , adj[v].push_back(mp(u,i));
    
    dfs(1);
    for (int i = 1 ; i <= m ; i ++){
        cin >> x[i];
        qu[i].resize(x[i]);
        for (int j = 0 ; j < x[i] ; j ++) cin >> qu[i][j];
        sort(qu[i].begin() , qu[i].end() , cmp);
        Roto = qu[i][0];
        for (int j = 1 ; j < x[i] ; j ++){
            P = __lca(qu[i][j-1] , qu[i][j]);
            dp[qu[i][j]] ++ , dp[P] --;
            if (d[Roto] > d[P]) dp[Roto] ++ , dp[P] -- , Roto = P;
        }
    }

    calc(1);
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
    cout << rt.size() << '\n';
    sort(rt.begin() , rt.end());
    for (auto u : rt) cout << u << ' ';

    return 0;
}

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