Submission #1291438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291438		hxian	Railway (BOI17_railway)	C++20	0 / 100	1097 ms	22340 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, val[100001], special[100001], depth[100001], finalv[100001];
int startnode, startdepth;
vector<int> adjList[100001];
vector<int> edges;
map<pair<int, int>, int> tracks;
bool dfs(int node, int last)
{
    bool out = false;
    bool all = true;
    int cnt = 0;
    for (int u : adjList[node])
        if (u != last)
        {
            ++cnt;
            bool t = dfs(u, node);
            out |= t;
            all &= t;
        }
    if (all || special[node])
    {
        if (special[node] || cnt > 1)
        {
            if (depth[node] < startdepth)
            {
                startnode = node;
                startdepth = depth[node];
            }
        }
    }
    if (special[node])
        out = true;
    if (!out)
        --val[node];
    return out;
}
void setdepth(int node, int last)
{
    depth[node] = depth[last] + 1;
    for (int u : adjList[node])
        if (u != last)
            setdepth(u, node);
}
void traverse(int node, int last, int curval)
{
    curval += val[node];
    finalv[node] = curval;
    for (int u : adjList[node])
        if (u != last)
            traverse(u, node, curval);
}
void recurse(int node, int last)
{
    for (int u : adjList[node])
        if (u != last)
        {
            if (min(finalv[u], finalv[node]) >= k)
                edges.push_back(tracks[{min(u, node), max(u, node)}]);
            recurse(u, node);
        }
}
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 = 0; i < m; i++)
    {
        memset(special, 0, sizeof(special));
        int s;
        cin >> s;
        for (int j = 0; j < s; j++)
        {
            int a;
            cin >> a;
            special[a] = 1;
        }
        startnode = 0;
        startdepth = INT_MAX;
        dfs(1, 0);
        ++val[startnode];
    }
    traverse(1, 0, 0);
    recurse(1, 0);
    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