Submission #1189708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189708		n3rm1n	Railway (BOI17_railway)	C++17	23 / 100	1098 ms	53176 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], 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);
    }
}

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];
}
map < int, int > st[maxn], fi[maxn];
int uni[maxn], ans[maxn];
map <int, int> dfs(int beg, int from)
{
    map < int, int > res;
    for (auto &[index, cnt]: st[beg])
        res[index] += cnt;

    for (auto &[nb, index]: g[beg])
    {
        if(nb == from)continue;
        map <int, int > mp = dfs(nb, beg);
        for (auto &[key, cnt]: mp)
            res[key] += cnt;
        ans[index] = uni[nb];
    }
    for (auto &[key, cnt]: fi[beg])
        res[key] -= cnt;
   // cout << "printing on " << beg << endl;
    for (auto &[key, cnt]: res)
    {
        if(!cnt)continue;
        uni[beg] ++;
        //cout << key << " " << cnt << endl;
    }
    return res;
}
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][i] ++;
        fi[last][i] += cnt;
       // 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: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25