Submission #889570

#	Time	Username	Problem	Language	Result	Execution time	Memory
889570		shiomusubi496	Railway (BOI17_railway)	C++17	100 / 100	129 ms	29320 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(v) begin(v), end(v)

using ll = long long;

struct edge {
    int to, id;
    edge(int to_, int id_) : to(to_), id(id_) {}
};

using Graph = vector<vector<edge>>;

class LowestCommonAncestor {
    int n, h;
    Graph G;
    vector<vector<int>> par;
    vector<int> ord, dep;
    int cnt = 0;

    void dfs(int v, int p) {
        par[0][v] = p;
        ord[v] = cnt++;
        for (auto e : G[v]) {
            if (e.to == p) continue;
            dep[e.to] = dep[v] + 1;
            dfs(e.to, v);
        }
    }

public:
    LowestCommonAncestor(Graph G_) : G(G_) {
        n = G.size();
        h = 1;
        while ((1 << h) < n) ++h;
        ++h;
        par.assign(h, vector<int>(n, -1));
        ord.resize(n);
        dep.resize(n); dep[0] = 0;
        cnt = 0;
        dfs(0, -1);
        rep (i, h - 1) rep (j, n) par[i + 1][j] = par[i][j] == -1 ? -1 : par[i][par[i][j]];
    }
    int lca(int a, int b) {
        if (dep[a] < dep[b]) swap(a, b);
        rrep (i, h) {
            if ((dep[a] - dep[b]) >> i & 1) a = par[i][a];
        }
        if (a == b) return a;
        rrep (i, h) {
            if (par[i][a] != par[i][b]) {
                a = par[i][a];
                b = par[i][b];
            }
        }
        return par[0][a];
    }
    int get_ord(int v) const { return ord[v]; }
};

int main() {
    int n, m, k; cin >> n >> m >> k;
    Graph g(n);
    rep (i, n - 1) {
        int a, b; cin >> a >> b;
        g[--a].emplace_back(--b, i);
        g[b].emplace_back(a, i);
    }
    LowestCommonAncestor lca(g);
    vector<int> imos(n);
    rep (i, m) {
        int s; cin >> s;
        vector<int> v(s);
        rep (j, s) cin >> v[j], --v[j];
        sort(all(v), [&](int a, int b) { return lca.get_ord(a) < lca.get_ord(b); });
        rep (j, s) {
            int a = v[j], b = v[(j + 1) % s];
            int c = lca.lca(a, b);
            ++imos[a]; ++imos[b];
            imos[c] -= 2;
        }
    }
    vector<int> ans;
    auto dfs = [&](auto&& self, int v, int p) -> void {
        for (auto e : g[v]) {
            if (e.to == p) continue;
            self(self, e.to, v);
            if (imos[e.to] >= k * 2) ans.push_back(e.id + 1);
            imos[v] += imos[e.to];
        }
    };
    dfs(dfs, 0, -1);
    sort(all(ans));
    cout << ans.size() << endl;
    rep (i, ans.size()) {
        cout << ans[i];
        if (i != ans.size() - 1) cout << " ";
    }
    cout << endl;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:101:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         if (i != ans.size() - 1) cout << " ";
      |             ~~^~~~~~~~~~~~~~~~~

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