Submission #1291439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291439		hxian	Railway (BOI17_railway)	C++20	0 / 100	1098 ms	60332 KiB

railway

// dmoj problem: https://vjudge.net/contest/765976#problem/G
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()
using namespace std;

int n, m, k, depth[100001], finalv[100001], parent[100001][20];
int startnode, startdepth;
vector<int> adjList[100001], add[100001], rm[100001];
vector<int> edges, specials;
map<pair<int, int>, int> tracks;
void setdepth(int node, int last)
{
    depth[node] = depth[last] + 1;
    parent[node][0] = last;
    for (int u : adjList[node])
        if (u != last)
            setdepth(u, node);
}
set<int> recurse(int node, int last)
{
    set<int> mayors;
    for (int u : add[node])
        mayors.insert(u);
    for (int u : adjList[node])
    {
        if (u != last)
        {
            for (int x : recurse(u, node))
                mayors.insert(x);
        }
    }
    finalv[node] = mayors.size();
    for (int u : rm[node])
        mayors.erase(u);
    return mayors;
}
bool allequal(vector<int> &check)
{
    bool allequal = true;
    for (int i = 1; i < check.size(); i++)
        allequal &= check[i] == check[0];
    return allequal;
}
int lca(vector<int> &nodes)
{
    int targetdepth = INT_MAX;
    for (int u : nodes)
        targetdepth = min(targetdepth, depth[u]);
    for (int i = 19; i >= 0; i--)
        for (int j = 0; j < nodes.size(); j++)
            if (depth[nodes[j]] - targetdepth >= (1 << i))
                nodes[j] = parent[nodes[j]][i];
    if (allequal(nodes))
        return nodes[0];
    for (int i = 19; i >= 0; i--)
    {
        vector<int> t;
        for (int j = 0; j < nodes.size(); j++)
            t.push_back(parent[j][i]);
        if (!allequal(t))
            swap(nodes, t);
    }
    return parent[nodes[0]][0];
}
int32_t main()
{
    cin.sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
        tracks[{min(a, b), max(a, b)}] = i;
    }
    setdepth(1, 0);
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= n; j++)
            parent[j][i] = parent[parent[j][i - 1]][i - 1];
    for (int i = 0; i < m; i++)
    {
        int s;
        cin >> s;
        specials.clear();
        for (int j = 0; j < s; j++)
        {
            int a;
            cin >> a;
            specials.push_back(a);
            add[a].push_back(i);
        }
        rm[lca(specials)].push_back(i);
    }
    recurse(1, 0);
    for (int i = 1; i <= n; i++)
    {
        for (int u : adjList[i])
            if (u > i && min(finalv[u], finalv[i]) >= k)
            {
                edges.push_back(tracks[{min(u, i), max(u, i)}]);
            }
    }
    cout << edges.size() << "\n";
    sort(all(edges));
    for (int u : edges)
        cout << u << " ";
    cout << "\n";

    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