Submission #922601

#	Time	Username	Problem	Language	Result	Execution time	Memory
922601		codefox	Railway (BOI17_railway)	C++14	100 / 100	529 ms	148284 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#pragma GCC target("popcnt")
#define pii pair<int, int>

vector<vector<pii>> graph;
vector<vector<int>> lift;
vector<int> depth;
vector<bitset<10000>> start;
vector<int> ende;
vector<int> minis;

void dfs(int i, int p, int d)
{
    depth[i] = d;
    for (pii ele:graph[i])
    {
        if (ele.first==p) continue;
        lift[0][ele.first] = i;
        dfs(ele.first, i, d+1);
    }
}

int finde(int a, int b)
{
    if (depth[a]<depth[b]) swap(a, b);
    int diff = depth[a]-depth[b];
    for (int i = 17; i >= 0; i--)
    {
        if (diff < (1<<i)) continue;
        diff -= 1<<i;
        a = lift[i][a];
    }
    if (a ==b) return a;
    for (int i = 17; i >= 0; i--)
    {
        if (lift[i][a]==lift[i][b]) continue;
        a = lift[i][a];
        b = lift[i][b];
    }
    return lift[0][a];
}

int dfs2(int i, int p)
{
    int e = ende[i];
    for (pii ele:graph[i])
    {
        if (ele.first == p) continue;
        int f = dfs2(ele.first, i);
        minis[ele.second] += start[ele.first].count()-f;
        start[i]|=start[ele.first];
        e+=f;
    }
    return e;
}

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

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m, k;
    cin >> n >> m >> k;

    graph.assign(n, vector<pii>());
    lift.assign(18, vector<int>(n, -1));
    depth.assign(n, 0);
    ende.assign(n, 0);
    start.assign(n, 0);
    minis.assign(n, 0);

    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back({b, i});
        graph[b].push_back({a, i});
    }
    dfs(0, -1, 0);

    for (int i = 1; i < 18; i++)
    {
        for (int j = 0;  j < n; j++)
        {
            int next = lift[i-1][j];
            if (next == -1) continue;
            lift[i][j] = lift[i-1][next];
        }
    }

    for (int i = 0; i <= m/10000; i++)
    {
        ende.assign(n, 0);
        start.assign(n, 0);
        for (int j = 0; j < min(10000, m-(i*10000)); j++)
        {
            int s;
            cin >> s;
            int lca =0;
            for (int h = 0; h < s; h++) 
            {
                int a;
                cin >> a;
                a--;
                if (h==0) lca = a;
                else lca = finde(a, lca);
                start[a][j] = 1;
            }
            ende[lca]++;
        }
        dfs2(0, -1);
    }
    vector<int> sol;
    
    for (int i = 0; i < n; i++)
    {
        if (minis[i]>=k) sol.push_back(i);
    }
    cout << sol.size() << "\n";
    for (int ele:sol) cout << ele << " ";

    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