Submission #491264

#	Time	Username	Problem	Language	Result	Execution time	Memory
491264		Rainbowbunny	Railway (BOI17_railway)	C++17	100 / 100	81 ms	35000 KiB

railway

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e5 + 5;
const int MAXL = 20;
 
int n, m, k, tim;
int tin[MAXN], tout[MAXN], ST[MAXL][2 * MAXN], H[MAXN], lg[2 * MAXN], f[MAXN], par[MAXN];
int Stack[MAXN], sz = 0;
vector <pair <int, int> > Adj[MAXN];
 
int Min(int x, int y)
{
    return H[x] > H[y] ? y : x; 
}
 
void DFS(int node, int p = -1)
{
    tim++;
    tin[node] = tim;
    ST[0][tim] = node;
    for(auto x : Adj[node])
    {
        if(x.first == p)
        {
            continue;
        }
        H[x.first] = H[node] + 1;
        par[x.first] = x.second;
        DFS(x.first, node);
        tim++;
        ST[0][tim] = node;
    }
    tout[node] = tim;
}
 
int LCA(int u, int v)
{
    int l = min(tin[u], tin[v]), r = max(tin[u], tin[v]);
    int tmp = lg[r - l + 1];
    return Min(ST[tmp][l], ST[tmp][r - (1 << tmp) + 1]);
}
 
bool Isparent(int u, int v)
{
    return tin[u] <= tin[v] and tout[u] >= tout[v];
}
 
void Update(int u, int v)
{
    if(H[v] < H[u])
    {
        swap(u, v);
    }
    // cout << u << ' ' << v << endl;
    assert(Isparent(u, v));
    f[u]--;
    f[v]++;
}
 
void DFS2(int node, int p = -1)
{
    for(auto x : Adj[node])
    {
        if(x.first == p)
        {
            continue;
        }
        DFS2(x.first, node);
        f[node] += f[x.first];
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    lg[0] = -1;
    for(int i = 1; i < MAXN; i++)
    {
        lg[i] = lg[i >> 1] + 1;
    }
    cin >> n >> m >> k;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].emplace_back(v, i);
        Adj[v].emplace_back(u, i);
    }
    DFS(1);
    for(int i = 1; i < MAXL; i++)
    {
        for(int j = 1; j + (1 << i) <= tim + 1; j++)
        {
            ST[i][j] = Min(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]);
        }
    }
    for(int i = 1; i <= m; i++)
    {
        int s;
        vector <int> V;
        cin >> s;
        V.resize(s);
        for(auto &x : V)
        {
            cin >> x;
        }
        sort(V.begin(), V.end(), [](int x, int y)
        {
            return tin[x] < tin[y];
        });
        int root = LCA(V[0], V.back());
        sz = 1;
        Stack[1] = root;
        for(auto x : V)
        {
            int oo = LCA(x, Stack[sz]);
            while(sz > 1 and !Isparent(Stack[sz - 1], oo))
            {
                Update(Stack[sz - 1], Stack[sz]);
                sz--;
            }
            if(Stack[sz - 1] == oo)
            {
                Update(Stack[sz - 1], Stack[sz]);
                sz--;
            }
            else
            {
                Update(oo, Stack[sz]);
                Stack[sz] = oo;
            }
            sz++;
            Stack[sz] = x;
        }
        for(int i = 1; i < sz; i++)
        {
            Update(Stack[i], Stack[i + 1]);
        }
    }
    DFS2(1);
    vector <int> Ans;
    for(int i = 2; i <= n; i++)
    {
        if(f[i] >= k)
        {
            Ans.push_back(par[i]);
        }
    }
    sort(Ans.begin(), Ans.end());
    cout << Ans.size() << '\n';
    for(auto x : Ans)
    {
        cout << x << ' ';
    }
    cout << '\n';
}

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