Submission #924551

#	Time	Username	Problem	Language	Result	Execution time	Memory
924551		Ghulam_Junaid	Railway (BOI17_railway)	C++17	100 / 100	287 ms	64848 KiB

railway

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const int LG = 17;

int n, m, k, a[N], h[N], par[N][LG], st[N], ft[N], tme;
vector<int> g[N];

void dfs(int v, int p = -1){
    st[v] = tme;
    tme++;

    for (int u : g[v]){
        if (u == p) continue;

        h[u] = h[v] + 1;
        par[u][0] = v;
        for (int i = 1; i < LG; i ++)
            if (par[u][i - 1] != -1)
                par[u][i] = par[par[u][i - 1]][i - 1];

        dfs(u, v);
    }
    ft[v] = tme;
}

int get_anc(int v, int d){
    for (int i = 0; i < LG; i ++)
        if ((1 << i) & d)
            v = par[v][i];
    return v;
}

int lca(int u, int v){
    if (h[u] > h[v])
        swap(u, v);

    v = get_anc(v, h[v] - h[u]);

    for (int i = LG - 1; i >= 0; i --)
        if (par[v][i] != par[u][i])
            v = par[v][i], u = par[u][i];

    return (u == v) ? v : par[v][0];
}

map<pair<int, int>, int> ind;
set<int> S[N], inside[N], ans;

void dfs_ans(int v, int p = -1){
    for (int u : g[v]){
        if (u == p) continue;
        dfs_ans(u, v);
        a[v] += a[u];

        if (S[v].size() < S[u].size())
            swap(S[u], S[v]);

        for (int x : S[u])
            S[v].insert(x);
        S[u].clear();
    }

    for (int x : inside[v])
        S[v].erase(x);

    if (S[v].size() >= k and ~p)
        ans.insert(ind[{p, v}]);
}

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

    cin >> n >> m >> k;

    for (int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
        ind[{u, v}] = ind[{v, u}] = i;
    }

    dfs(1);

    for (int i = 0; i < m; i ++){
        int x;
        cin >> x;

        int L = 0;
        for (int j = 0; j < x; j ++){
            int v;
            cin >> v;

            S[v].insert(i);
            if (!L)
                L = v;
            else
                L = lca(L, v);
        }
        
        a[L]++;
        inside[L].insert(i);
    }

    dfs_ans(1);

    cout << ans.size() << endl;
    for (int x : ans)
        cout << x << " ";
    cout << endl;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs_ans(int, int)':
railway.cpp:68:21: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |     if (S[v].size() >= k and ~p)
      |         ~~~~~~~~~~~~^~~~

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