Submission #1189709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189709		n3rm1n	Railway (BOI17_railway)	C++17	100 / 100	179 ms	63656 KiB

railway

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const int maxn = 1e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m, k;
vector < pair < int, int > > g[maxn];

int p[maxn], pindex[maxn], depth[maxn];
void dfs0(int beg, int from)
{
    p[beg] = from;
    depth[beg] = depth[from] + 1;
    for (auto &[nb, id]: g[beg])
    {
        if(nb == from)continue;
        dfs0(nb, beg);
        pindex[nb] = id;
    }
}

int jump[maxn][20];
int moveup(int v, int x)
{
    for (int i = 0; i < 20; ++ i)
        if(x & (1 << i))v = jump[v][i];
    return v;
}
int lca(int u, int v)
{
    //cout << "getting lca " << u << " and " << v << endl;
    if(depth[u] < depth[v])swap(u, v);
    int diff = depth[u] - depth[v];
    u = moveup(u, diff);
    // cout << "* " << u << " " << v << endl;
    if(u == v)return u;
    for (int i = 19; i>= 0; -- i)
    {
        int newu = jump[u][i];
        int newv = jump[v][i];
        if(newu && newv && newv != newu)
        {
            u = newu;
            v = newv;
        }
    }
    return p[u];
}
set < int > st[maxn], fi[maxn];
int uni[maxn], ans[maxn];
set < int > keep[maxn];
bool cmp(int a, int b)
{
    return (keep[a].size() > keep[b].size());
}

void dfs(int beg, int from)
{
    set < int > res;


    vector < int > u;
    for (auto &[nb, index]: g[beg])
    {
        if(nb == from)continue;
        u.pb(nb);
        dfs(nb, beg);
    }
    if(u.size() > 0)
    {
        sort(u.begin(), u.end(), cmp);
        swap(res, keep[u[0]]);
        for (int i = 1; i < u.size(); ++ i)
        {
            int nb = u[i];
            for (auto key: keep[nb])
                res.insert(key);
        }


    }
    for (auto key: st[beg])
        res.insert(key);
    for (auto key: fi[beg])
        res.erase(key);

    ans[pindex[beg]] = res.size();
    swap(res, keep[beg]);
}
int main()
{
    speed();

    cin >> n >> m >> k;
    for (int i = 1; i < n; ++ i)
    {
        int uu, vv;
        cin >> uu >> vv;
        g[uu].pb(make_pair(vv, i));
        g[vv].pb(make_pair(uu, i));
    }
    dfs0(1, 0);
    for (int i = 1; i <= n; ++ i)
        jump[i][0] = p[i];
    for (int j = 1; j < 20; ++ j)
    {
        for (int i = 1; i <= n; ++ i)
            jump[i][j] = jump[jump[i][j-1]][j-1];
    }
    for (int i = 1; i <= m; ++ i)
    {
        int cnt;
        cin >> cnt;
        vector < int > s;
        int last;
        cin >> last;
        s.pb(last);
        for (int j = 1; j < cnt; ++ j)
        {
            int v;
            cin >> v;
            s.pb(v);
            last = lca(last, v);
        }
        for (auto v: s)
            st[v].insert(i);
        fi[last].insert(i);
        // cout << "lca is "<<last << endl;
    }
    dfs(1, 0);
    vector < int > make;
    for (int i = 1; i < n; ++ i)
    {
        if(ans[i] >= k)make.pb(i);
    }
    cout << make.size() << endl;
    for (auto x: make)
        cout << x << " ";
    cout << endl;
    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