제출 #1365078

#제출 시각아이디문제언어결과실행 시간메모리
1365078goppamachRailway (BOI17_railway)C++20
100 / 100
38 ms22184 KiB
#include <bits/stdc++.h>

using namespace std;

#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x) * (x))
#define FOR(i, l, r) for (int i = l; i <= (r); i++)
#define FOD(i, l, r) for (int i = l; i >= (r); i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) ((int)(x).size())
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;

template <typename T>
using heap = priority_queue<T>;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

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

// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.h"
#else
#define debug(...)
#define debug_arr(...)
#endif

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 1E5 + 5, LG = 17;
constexpr int INF = 1E9 + 7;
constexpr ll INFLL = 4E18;
constexpr int MOD = 1E9 + 7; // 998244353
constexpr db EPS = 1E-10;
constexpr ld PI = 3.14159265358979323846;
constexpr int PRECISION = 10;

int n, m, k;
vi adj[N];
pii edges[N];
int tin[N], tout[N];
int up[N][LG + 1];
int pref[N];
int cnt = 0;

void dfs(int u, int p) {
    tin[u] = ++cnt;
    up[u][0] = p;
    FOR(e, 1, LG) {
        up[u][e] = up[up[u][e - 1]][e - 1];
    }
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
    tout[u] = cnt;
}

bool anc(int root, int u) {
    return tin[root] <= tin[u] && tout[u] <= tout[root];
}

int lca(int u, int v) {
    if (anc(u, v)) return u;
    if (anc(v, u)) return v;
    FOD(e, LG, 0) {
        if (!anc(up[u][e], v)) {
            u = up[u][e];
        }
    }
    return up[u][0];
}

void dfs_pref(int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            dfs_pref(v, u);
            pref[u] += pref[v];
        }
    }
}

void solve() {
    cin >> n >> m >> k;

    FOR(i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges[i] = {u, v};
    }

    dfs(1, 1);

    while (m--) {
        int s;
        cin >> s;
        vi q(s);
        FOR(i, 0, s - 1) cin >> q[i];
        sort(all(q), [&](int u, int v) { return tin[u] < tin[v]; });
        FOR(i, 0, s - 1) {
            int u = q[i], v = q[(i + 1) % s];
            pref[u]++;
            pref[v]++;
            pref[lca(u, v)] -= 2;
        }
    }

    dfs_pref(1, 1);

    vi res;
    FOR(i, 1, n - 1) {
        auto [u, v] = edges[i];
        if (tin[u] < tin[v]) swap(u, v);
        if (pref[u] >= 2 * k) {
            res.push_back(i);
        }
    }

    cout << sz(res) << el;
    for (int id : res) cout << id << " ";
}

int main() {
    fast_io
    #define LOCAL
    #ifndef LOCAL
    #define PROBLEM ""
    freopen(PROBLEM ".INP", "r", stdin);
    freopen(PROBLEM ".OUT", "w", stdout);
    #endif

    int t = 1;
    // cin >> t;
    while (t--) solve();
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…