Submission #1096038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096038		cpismylifeOwO	Railway (BOI17_railway)	C++17	100 / 100	70 ms	28140 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e5 + 5;
const int MaxLog = 18;

struct Edge
{
    int u, v;
};

int n, m, k;
Edge edges[MaxN];
vector<int> graph[MaxN];

void Inp()
{
    cin >> n >> m >> k;
    for (int x = 1; x < n; x++)
    {
        cin >> edges[x].u >> edges[x].v;
        graph[edges[x].u].push_back(x);
        graph[edges[x].v].push_back(x);
    }
}

int curDFS;
int euler[MaxN];
int ending[MaxN];
int h[MaxN];
int par[MaxN];

void PreDFS(int u, int p)
{
    curDFS++;
    euler[u] = curDFS;
    for (int x : graph[u])
    {
        int v = edges[x].u ^ edges[x].v ^ u;
        if (v != p)
        {
            h[v] = h[u] + 1;
            par[v] = u;
            PreDFS(v, u);
        }
    }
    ending[u] = curDFS;
}

int BinLift[MaxLog][MaxN];

void Build()
{
    for (int x = 1; x <= n; x++)
    {
        BinLift[0][x] = par[x];
    }
    for (int x = 1; x < MaxLog; x++)
    {
        for (int y = 1; y <= n; y++)
        {
            BinLift[x][y] = BinLift[x - 1][BinLift[x - 1][y]];
        }
    }
}

int LCA(int u, int v)
{
    if (h[u] != h[v])
    {
        if (h[u] > h[v])
        {
            swap(u, v);
        }
        int k = h[v] - h[u];
        for (int x = MaxLog - 1; x >= 0; x--)
        {
            if (k & (1 << x))
            {
                v = BinLift[x][v];
            }
        }
    }
    if (u == v)
    {
        return v;
    }
    for (int x = MaxLog - 1; x >= 0; x--)
    {
        if (BinLift[x][u] != BinLift[x][v])
        {
            u = BinLift[x][u];
            v = BinLift[x][v];
        }
    }
    return par[u];
}

int sum[MaxN];
int query[2 * MaxN];
vector<int> res;

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

void DFS(int u, int p)
{
    for (int x : graph[u])
    {
        int v = edges[x].u ^ edges[x].v ^ u;
        if (v != p)
        {
            DFS(v, u);
            if (sum[v] >= k)
            {
                res.push_back(x);
            }
            sum[u] += sum[v];
        }
    }
}

void Exc()
{
    curDFS = 0;
    PreDFS(1, -1);
    Build();
    for (int x = 1; x <= m; x++)
    {
        int p;
        cin >> p;
        vector<int> tmp;
        for (int x = 1; x <= p; x++)
        {
            cin >> query[x];
            tmp.push_back(query[x]);
        }
        sort(query + 1, query + p + 1, cmp);
        for (int x = 2; x <= p; x++)
        {
            tmp.push_back(LCA(query[x - 1], query[x]));
        }
        sort(tmp.begin(), tmp.end(), cmp);
        stack<int> st;
        for (int x = 0; x < (int)tmp.size(); x++)
        {
            int y = x;
            while (y < (int)tmp.size() && tmp[x] == tmp[y])
            {
                y++;
            }
            y--;
            sum[tmp[x]]++;
            while (!st.empty() && !(euler[st.top()] <= euler[tmp[x]] && euler[tmp[x]] <= ending[st.top()]))
            {
                st.pop();
            }
            if (st.empty())
            {
                sum[tmp[x]]--;
            }
            else
            {
                sum[st.top()]--;
            }
            st.push(tmp[x]);
            x = y;
        }
    }
    DFS(1, -1);
    sort(res.begin(), res.end());
    cout << (int)res.size() << "\n";
    for (int x : res)
    {
        cout << x << " ";
    }
}

int main()
{
    //freopen("D.INP", "r", stdin);
    //freopen("D.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    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