Submission #363956

#	Time	Username	Problem	Language	Result	Execution time	Memory
363956		ngpin04	Railway (BOI17_railway)	C++14	100 / 100	162 ms	24716 KiB

railway

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5;

vector <int> ans;
vector <pair <int, int>> adj[N];

int anc[20][N];
int id[N];
int bit[N];
int tin[N];
int tout[N];
int n,k,q,cntdfs;

void update(int pos, int val)
{
    for (; pos <= n; pos += pos & -pos)
        bit[pos] += val;
}

int getsum(int l, int r)
{
    int res = 0;
    for (; r > 0; r -= r & -r)
        res += bit[r];

    for (l--; l > 0; l -= l & -l)
        res -= bit[l];

    return res;
}

bool isanc(int p, int u)
{
    return tin[p] <= tin[u] && tout[u] <= tout[p];
}

int getlca(int u, int v)
{
    if (isanc(u, v))
        return u;
    for (int i = 19; i >= 0; i--)
        if (anc[i][u] > 0 && !isanc(anc[i][u], v))
            u = anc[i][u];
    return anc[0][u];
}

void dfs(int u, int p)
{
    anc[0][u] = p;
    for (int i = 1; i < 20; i++)
    {
        int par = anc[i - 1][u];
        anc[i][u] = (par < 0) ? -1 : anc[i - 1][par];
    }

    tin[u] = ++cntdfs;

    for (pair <int, int> to : adj[u])
    {
        int v = to.fi;
        if (v == p)
            continue;
        id[v] = to.se;
        dfs(v, u);
    }
    tout[u] = cntdfs;
}

void query(int u, int v)
{
    int p = getlca(u, v);
    update(tin[u], 1);
    update(tin[v], 1);
    update(tin[p], -2);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    cin >> n >> q >> k;
    for (int i = 1; i < n; i++)
    {
        int u,v;
        cin >> u >> v;
        adj[u].push_back(mp(v, i));
        adj[v].push_back(mp(u, i));
    }

    dfs(1, -1);

    for (int i = 1; i <= q; i++)
    {
        int m;
        cin >> m;
        vector <int> a(m);
        for (int &x : a)
            cin >> x;

        sort(a.begin(), a.end(), [](int i, int j) {return tin[i] < tin[j];});
        for (int i = 0; i < m; i++)
            query(a[i], a[(i + 1) % m]);
    }

    for (int i = 2; i <= n; i++)
        if (getsum(tin[i], tout[i]) >= 2 * k)
            ans.push_back(id[i]);

    sort(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for (int x : ans)
        cout << x << " ";
    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