Submission #171297

#	Time	Username	Problem	Language	Result	Execution time	Memory
171297		parsa_mobed	Railway (BOI17_railway)	C++14	100 / 100	231 ms	26336 KiB

railway

#include <bits/stdc++.h>

using namespace std;
#define pii pair <int , int>
#define F first
#define S second

const int N = 2e5 + 10, LOG = 20;
int h[N], par[N][LOG], cnt[N], val[N], st[N], timer = 0;
vector <pii> g[N];

void dfs(int v, int pr = 0)
{
    h[v] = h[pr] + 1;
    st[v] = timer++;
    par[v][0] = pr;
    for (int i = 1; i < LOG; i++) par[v][i] = par[par[v][i - 1]][i - 1];
    for (auto p : g[v]) if (p.F != pr) dfs(p.F, v);
}

int getpar(int v, int height)
{
    for (int i = 0; i < LOG; i++) if (height & (1 << i)) v = par[v][i];
    return v;
}

int LCA(int u, int v)
{
    if (h[v] < h[u]) swap(u, v);
    v = getpar(v, h[v] - h[u]);
    if (u == v) return v;
    for (int i = LOG - 1; i >= 0; i--) if (par[v][i] != par[u][i]) v = par[v][i], u = par[u][i];
    return par[v][0];
}

int solve(int v, int pr = 0, int ID = 0)
{
    int VAL = val[v];
    for (auto p : g[v]) if (p.F != pr) {
        int u = p.F, id = p.S;
        VAL += solve(u, v, id);
    }
    return cnt[ID] = VAL;
}

bool cmp(int i, int j) {return st[i] < st[j];}

int32_t main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k, q; cin >> n >> q >> k;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    dfs(1);
    while (q--) {
        int s; cin >> s;
        vector <int> vec;
        for (int i = 0; i < s; i++) {
            int u; cin >> u; val[u]++;
            vec.push_back(u);
        }
        sort(vec.begin(), vec.end(), cmp);
        for (int i = 0; i < s - 1; i++) {
            val[LCA(vec[i], vec[i + 1])]--;
        }
        val[LCA(vec[0], vec[s - 1])]--;
    }
    solve(1);
    vector <int> ans;
    for (int i = 1; i < n; i++) if (cnt[i] >= k) ans.push_back(i);
    cout << ans.size() << "\n";
    for (int i : ans) cout << i << " ";
    cout << "\n";

    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