Submission #1085030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085030		TheGreatAntivirus	Railway (BOI17_railway)	C++17	100 / 100	77 ms	44740 KiB

railway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define stdI freopen("input.txt", "r", stdin);
#define stdO freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()
#define mp(x, y) make_pair(x, y)
#define int long long
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;

typedef tree<int,
    null_type,less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;

typedef pair<int, int> pii;

const int MAXN = 2e5 + 100, MAXLOG = 20, INF = 1e18, MOD = 1e9 + 7;

struct ad
{
    int u, i;
};

vector<ad> adj[MAXN];
vector<int> ans;
int st[MAXN], h[MAXN], par[MAXN][MAXLOG], cnt[MAXN];
int n, m, k, t;

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

void predfs(int v, int p)
{
    par[v][0] = p;
    st[v] = ++t;
    for(int i = 1; i < MAXLOG; i++)
    {
        par[v][i] = par[par[v][i - 1]][i - 1];
    }
    for(auto u : adj[v])
    {
        if(u.u != p)
        {
            h[u.u] = h[v] + 1;
            predfs(u.u, v);
        }
    }
    t++;
}

int lca(int u, int v)
{
    if(h[u] < h[v])
    {
        swap(u, v);
    }
    for(int i = MAXLOG - 1; i > -1; i--)
    {
        if(h[par[u][i]] >= h[v])
        {
            u = par[u][i];
        }
    }
    if(u == v)
    {
        return v;
    }
    for(int i = MAXLOG - 1; i > -1; i--)
    {
        if(par[u][i] != par[v][i])
        {
            u = par[u][i]; v = par[v][i];
        }
    }
    return par[u][0];
}

void dfs(int v, int p, int ip)
{
    for(auto u : adj[v])
    {
        if(u.u != p)
        {
            dfs(u.u, v, u.i);
            cnt[v] += cnt[u.u];
        }
    }
    if(cnt[v] >= 2 * k && v != 1)
    {
        ans.push_back(ip);
    }
}

void solve()
{
    cin >> n >> m >> k; h[0] = -INF;
    for(int i = 1; i < n; i++)
    {
        int u, v; cin >> u >> v;
        adj[u].push_back({v, i}); adj[v].push_back({u, i});
    }
    predfs(1, 0);
    for(int i = 0; i < m; i++)
    {
        int w; cin >> w;
        int t[w];
        for(int j = 0; j < w; j++)
        {
            cin >> t[j];
        }
        sort(t, t + w, cmp);
        for(int j = 1; j < w; j++)
        {
            cnt[t[j]]++; cnt[t[j - 1]]++;
            cnt[lca(t[j], t[j - 1])] -= 2;
        }
        cnt[t[0]]++; cnt[t[w - 1]]++;
        cnt[lca(t[0], t[w - 1])] -= 2;
    }
    dfs(1, 0, 0);
    cout << ans.size() << "\n";
    sort(all(ans));
    for(auto x : ans)
    {
        cout << x << " ";
    }
    cout << "\n";
}

int32_t main()
{
    IOS;
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
    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