Submission #874982

#	Time	Username	Problem	Language	Result	Execution time	Memory
874982		loggerr	Railway (BOI17_railway)	C++14	100 / 100	156 ms	42564 KiB

railway

#include "bits/stdc++.h"
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...)
#endif

#define sz(a) (int)(a).size()
//#define int int64_t

using namespace std;
using ll = int64_t;
using ld = long double;

const int INFi = 1e9 + 10;
const ll INFl = (ll)1e18 + 228;

template<class T>
bool inmin(T& a, T b) {
    return (a > b ? a = b, true : false);
}

template<class T>
bool inmax(T& a, T b) {
    return (a < b ? a = b, true : false);
}

void solve_case();

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed << setprecision(10);
#ifdef LOCAL
    freopen("read.txt", "r", stdin);
#endif
    int tc = 1;
    //cin >> tc;
    while (tc--) solve_case();
}
vector<vector<int>> gr;
void add_edge(int u, int v) {
    gr[u].push_back(v);
    gr[v].push_back(u);
}

struct binup {
    int Log = 20;
    vector<vector<int>> up;
    vector<int> dep;

    binup(int n) {
        up.resize(Log, vector<int> (n));
        dep.resize(n, -1);
    }

    void calc_dfs(int v, int p, const vector<vector<int>> &gr) {
        dep[v] = dep[p] + 1;
        up[0][v] = p;
        for (int adj : gr[v]) {
            if (adj == p) continue;
            calc_dfs(adj, v, gr);
        }
    }

    binup(const vector<vector<int>> &gr, int root) : binup(sz(gr)) {
        calc_dfs(root, root, gr);
        calc();
    }

    void set_par(int v, int p) {
        assert(!up.empty());
        up[0][v] = p;
    }

    void calc() {
        for (int k = 1; k < Log; ++k) {
            for (int v = 0; v < (int)up[0].size(); ++v) {
                up[k][v] = up[k - 1][up[k - 1][v]];
            }
        }
    }

    int get_dep(int v) {
        return dep[v];
    }

    int la(int v, int k) { // level ancestor
        for (int i = 0; i < Log; ++i) {
            if (k & (1 << i)) {
                v = up[i][v];
            }
        }
        return v;
    }

    int lca(int u, int v) {
        if (dep[u] < dep[v]) swap(u, v);
        u = la(u, dep[u] - dep[v]);
        if (u == v) return u;
        for (int k = Log - 1; k >= 0; --k) {
            if (up[k][u] != up[k][v]) {
                u = up[k][u], v = up[k][v];
            }
        }
        return up[0][u];
    }

};


vector<int> tin, tout;
int timer;
int k;

void dfs(int v, int p) {
    tin[v] = timer++;
    for (int adj : gr[v]) {
        if (adj == p) continue;
        dfs(adj, v);
    }
    tout[v] = timer++;
}

vector<int> dp;
map<pair<int, int>, int> mp;
vector<int> ans;

void calc_dp(int v, int p) {
    for (int adj : gr[v]) {
        if (adj == p) continue;
        calc_dp(adj, v);
        if (dp[adj] >= k) {
            ans.push_back(mp[{v, adj}]);
        }
        dp[v] += dp[adj];
    }
}

void solve_case() {
    int n, m;
    cin >> n >> m >> k;
    gr.assign(n, {});
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        add_edge(u, v);
        mp[{u, v}] = mp[{v, u}] = i;
    }
    binup up(gr, 0);
    tin.resize(n), tout.resize(n);
    timer = 0;
    dfs(0, 0);
    dp.assign(n, 0);
    for (int i = 0; i < m; ++i) {
        int s; cin >> s;
        vector<int> vertex(s);
        struct event {
            int x, v, tp;
            event(int _x, int _v, int _tp) : x(_x), v(_v), tp(_tp) {}
        };
        vector<event> e;
        for (int j = 0; j < s; ++j) {
            cin >> vertex[j];
            --vertex[j];
            e.emplace_back(tin[vertex[j]], vertex[j], 1);
            e.emplace_back(tout[vertex[j]], vertex[j], -1);
        }
        sort(vertex.begin(), vertex.end(), [&](const int &u, const int &v) {
            return tin[u] < tin[v];
        });
        for (int j = 0; j + 1 < sz(vertex); ++j) {
            int lca = up.lca(vertex[j], vertex[j + 1]);
            e.emplace_back(tin[lca], lca, 1);
            e.emplace_back(tout[lca], lca, -1);
        }
        sort(e.begin(), e.end(), [&](const event &a, const event &b) {
            return a.x < b.x;
        });
        stack<int> st;
        for (auto [x, v, tp] : e) {
            if (tp == -1) {
                st.pop();
            } else {
                if (!st.empty()) {
                    dp[st.top()]--;
                    dp[v]++;
                }
                st.push(v);
            }
        }
    }
    calc_dp(0, 0);
    cout << sz(ans) << '\n';
    sort(ans.begin(), ans.end());
    for (int i : ans) {
        cout << i + 1 << ' ';
    }
    cout << '\n';
}

Compilation message (stderr)

railway.cpp: In function 'void solve_case()':
railway.cpp:181:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  181 |         for (auto [x, v, tp] : e) {
      |                   ^

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