Submission #878255

#	Time	Username	Problem	Language	Result	Execution time	Memory
878255		Soshi85	Railway (BOI17_railway)	C++14	0 / 100	60 ms	23236 KiB

railway

#include<bits/stdc++.h>
     
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
 
#define pb              push_back
#define F               first
#define S               second
//#define mp              make_pair
#define all(x)          x.begin(),x.end()
#define file            freopen("closing.in", "r", stdin);freopen("closing.out", "w", stdout);
#define kill(x)         {cout << x << '\n'; return 0;}
//#define int                ll

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2")

const int N =  1e5 + 110, LG = 18, MOD = 1e9+9;
const ll inf = 1e12;

int n, m, k, d[N], anc[N][LG], dp[N];
vector<int> g[N];
vector<pii> edge;

void dfs(int v = 0, int p = -1) {
    for(int i = 1; i < LG; ++i) anc[v][i] = anc[anc[v][i-1]][i-1];
    for(int u : g[v]) {
        if(u ^ p) {
            anc[u][0] = v;
            d[u] = d[v] + 1;
            dfs(u, v);
        }
    }
}

int dfS(int v = 0, int p = -1) {
    int sum = 0;

    for(int u : g[v])
        if(u ^ p) 
            sum += dfS(u, v);

    sum += dp[v];
    dp[v] = sum; 
    return sum;
}

inline int lca (int v, int u) {
    
    if(v == u) return v;
    if(d[v] < d[u]) swap(u, v);
 
    int dist = d[v] - d[u];
    for(int i = 0; i < LG; ++i)
        if(dist & (1 << i)) v = anc[v][i];

    if(u == v) return v;
 
    while(u != v) {
        int l = 0, r = LG;
        while(r-l > 1) {
            int mid = (r+l) / 2;
            if(anc[u][mid] == anc[v][mid]) r = mid;
            else l = mid;
 
        }
        u = anc[u][l], v = anc[v][l];
    }
 
    return v;
    
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
        
    cin >> n >> m >> k;

    for(int i = 0; i < n-1; ++i) {
        int v, u;
        cin >> v >> u;
        g[--v].pb(--u);
        g[u].pb(v);
        edge.pb({u, v});
    }
    
    dfs();

    for(int i = 0; i < m; ++i) {
        int sz;
        cin >> sz;
        vector<int> v;
        for(int j = 0; j < sz; ++j) {
            int x;
            cin >> x;
            v.pb(x);
        }
        for(int i = 1; i < (int) v.size(); ++i) {
            int LCA = lca(v[0], v[i]);
            ++dp[v[0]]; ++dp[v[i]]; dp[LCA] -= 2;
        }
    }
    
    dfS();
    
    for(int i = 0; i < n-1; ++i) {
        if(d[edge[i].F] < d[edge[i].S]) swap(edge[i].F, edge[i].S);
    }

    vector<int> ans;
    for(int i = 0; i < n-1; ++i) {
        if(dp[edge[i].F] >= k)
            ans.pb(i+1);
    }
    
    cout << ans.size() << '\n';
    
    for(int i : ans) {
        cout << i << ' ';
    }

    return 0;
}

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