Submission #321991

#	Time	Username	Problem	Language	Result	Execution time	Memory
321991		ThaiBaHung	Railway (BOI17_railway)	C++14	100 / 100	419 ms	35684 KiB

railway

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
int n, m, k;
vector < int > adj[N];
struct E
{
    int id;
    int u;
    int v;
};
E edge[N];

int numchain;
int ChainId[N];
int ChainHead[N];
int cha[N];
int P[N][30];
int pos[N];
int dinh[N];
int socon[N];
int dem = 0;
int depth[N];
int vs[N];
pair < int, int > point[N];
int pre[N];

void dfs(int i, int j)
{
    socon[i] = 1;
    P[i][0] = j;
    depth[i] = depth[j] + 1;

    for (int u : adj[i])
    {
        if (u == j) continue;
        dfs(u, i);
        socon[i] += socon[u];
    }
}

void hld(int i, int j)
{
    if (!ChainHead[numchain])  ChainHead[numchain] = i;
    ChainId[i] = numchain;

    dem++;
    pos[i] = dem;
    dinh[dem] = i;

    int cur = -1;

    for (int u : adj[i])
    {
        if (u == j) continue;

        if (cur == -1 || socon[u] > socon[cur])
            cur = u;
    }

    if (cur != -1) hld(cur, i);

    for (int u : adj[i])
    {
        if (u == j) continue;
        if (u == cur) continue;

        numchain++;
        hld(u, i);
    }
}

void build_rmq()
{
    for (int k = 1; k <= log2(n); k++)
        for (int i = 1; i <= n; i++)
            P[i][k] = P[P[i][k - 1]][k - 1];
    return;
}

int jump(int u, int h)
{
    for (int k = log2(n); k >= 0; k--)
    {
        if (h >= (1 << k))
        {
            u = P[u][k];
            h -= (1 << k);
        }
    }

    return u;
}

int LCA(int u, int v)
{
    if (depth[u] > depth[v]) swap(u, v);

    v = jump(v, depth[v] - depth[u]);

    if (u == v) return u;

    for (int k = log2(n); k >= 0; k--)
    {
        if (P[u][k] != P[v][k])
        {
            u = P[u][k];
            v = P[v][k];
        }
    }

    return P[u][0];
}

struct ok
{
    int lo;
    int hi;
    int val;
    int lazy;
};
ok Node[4 * N];

void build(int id, int l, int r)
{
    Node[id].lo = l;
    Node[id].hi = r;

    if (l == r) return;

    int mid = (l + r) / 2;

    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
}

void down(int id)
{
    int t = Node[id].lazy;

    Node[id * 2].lazy += t;
    Node[id * 2].val += t;

    Node[id * 2 + 1].lazy += t;
    Node[id * 2 + 1].val += t;

    Node[id].lazy = 0;
}

void update(int id, int l, int r, int val)
{
    if (Node[id].lo > r || Node[id].hi < l) return;

    if (l <= Node[id].lo && Node[id].hi <= r)
    {
        Node[id].lazy += val;
        Node[id].val += val;
        return;
    }

    down(id);

    update(id * 2, l, r, val);
    update(id * 2 + 1, l, r, val);

    Node[id].val = Node[id * 2].val + Node[id * 2 + 1].val;
}

int getval(int id, int pos)
{
    if (Node[id].lo > pos || Node[id].hi < pos) return 0;

    if (Node[id].lo == Node[id].hi)
        return Node[id].val;

    down(id);

    return max(getval(id * 2, pos), getval(id * 2 + 1, pos));
}

void solve(int u, int top)
{

    while (ChainId[u] != ChainId[top])
    {
        int id = ChainId[u];
        int nxt = ChainHead[id];

        update(1, pos[nxt], pos[u], 1);

        u = P[nxt][0];
    }

    update(1, pos[top] + 1, pos[u], 1);

    return;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("t.inp","r",stdin); freopen("t.out","w",stdout);

    cin >> n >> m >> k;

    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[i].id = i; edge[i].u = u; edge[i].v = v;
        adj[u].push_back(v); adj[v].push_back(u);
    }

    dfs(1, 1);

    numchain = 1;

    hld(1, 0);

    build_rmq();

    build(1,1,n);

    for (int i = 1; i <= m; i++)
    {
        int cnt;
        cin >> cnt;
        cin >> point[1].second;

        point[1].first = pos[point[1].second];

        int top = point[1].second;

        for (int j = 2; j <= cnt; j++)
        {
            cin >> point[j].second;
            top = LCA(top, point[j].second);
            point[j].first = pos[point[j].second];
        }

        sort(point + 1, point + cnt + 1);

        solve(point[1].second, top);

        for (int j = 2; j <= cnt; j++)
        {
            int cur = LCA(point[j].second, point[j - 1].second);
            solve(point[j].second, cur);
        }
    }

    vector < int > ans;

    for (int i = 1; i < n; i++)
    {
        int u = edge[i].u;
        int v = edge[i].v;

        if (u == P[v][0]) swap(u, v);

        if (getval(1, pos[u]) >= k) ans.push_back(i);

        //cout << u << " " << pos[u] << " " << getval(1, pos[u]) << '\n';
    }

    cout << ans.size() << '\n';

    for (int u : ans)
        cout << u << " ";
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25