Submission #223756

#	Time	Username	Problem	Language	Result	Execution time	Memory
223756		johutha	Railway (BOI17_railway)	C++17	100 / 100	242 ms	61036 KiB

railway

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

#define int int64_t

using namespace std;

int log2(int n)
{
    int r = 0;
    for (; n; n /= 2) r++;
    return r;
}

struct tree
{
    int n;
    vector<vector<int>> adjlist;
    vector<vector<int>> st;
    vector<vector<int>> en;
    vector<int> res;

    set<int>* smldfs(int curr, int par)
    {
        set<int>* rs = new set<int>(st[curr].begin(), st[curr].end());
        
        for (auto next : adjlist[curr])
        {
            if (next == par) continue;
            set<int>* ot = smldfs(next, curr);
            if (ot->size() > rs->size()) swap(ot, rs);
            for (auto i : (*ot))
            {
                rs->insert(i);
            }
        }
        for (auto i : en[curr])
        {
            rs->erase(i);
        }
        res[curr] = rs->size();
        return rs;
    }

    vector<vector<int>> table;
    vector<int> lvl;
    int logn;

    void dfs(int curr, int par, int lv)
    {
        lvl[curr] = lv;
        table[0][curr] = par;
        for (auto next : adjlist[curr]) if (next != par) dfs(next, curr, lv + 1);
    }

    void prelca()
    {
        logn = log2(n) + 1;
        table.resize(logn, vector<int>(n));
        lvl.resize(n);
        dfs(0, -1, 0);

        for (int i = 1; i < logn; i++)
        {
            for (int j = 0; j < n; j++)
            {
                table[i][j] = (table[i - 1][j] == -1 ? -1 : table[i - 1][table[i - 1][j]]);
            }
        }
    }

    int lca(int a, int b)
    {
        if (lvl[a] < lvl[b]) swap(a, b);
        int ld = lvl[a] - lvl[b];

        for (int j = 0; j < logn; j++)
        {
            if (ld & (1<<j)) a = table[j][a];
        }
        if (a == b) return a;
        for (int j = logn - 1; j >= 0; j--)
        {
            if (table[j][a] != table[j][b])
            {
                a = table[j][a];
                b = table[j][b];
            }
        }
        return table[0][a];
    }
};

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

    tree t;
    t.n = n;
    t.adjlist.resize(n);
    vector<pair<int,int>> edges;

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

    t.prelca();
    t.st.resize(n);
    t.en.resize(n);

    for (int i = 0; i < m; i++)
    {
        int c;
        cin >> c;
        int l = -1;
        for (int j = 0; j < c; j++)
        {
            int a;
            cin >> a;
            a--;
            t.st[a].push_back(i);
            if (l == -1) l = a;
            else l = t.lca(l, a);
        }
        t.en[l].push_back(i);
    }
    t.res.resize(n);
    t.smldfs(0, -1);

    vector<int> sol;
    for (int i = 0; i < n - 1; i++)
    {
        auto e = edges[i];
        int a = (t.lvl[e.first] > t.lvl[e.second] ? e.first : e.second);
        if (t.res[a] >= k) sol.push_back(i + 1);
    }
    cout << sol.size() << "\n";
    for (auto i : sol) cout << i << " ";
    cout << "\n";
}

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