제출 #1365074

#제출 시각아이디문제언어결과실행 시간메모리
1365074goppamachRailway (BOI17_railway)C++20
36 / 100
45 ms22060 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], pref[N];
int up[N][LG + 1], depth[N];
int cnt = 0;

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

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    FOD(e, LG, 0) {
        if (depth[u] - (1 << e) >= depth[v]) {
            u = up[u][e];
        }
    }
    if (u == v) return u;
    FOD(e, LG, 0) {
        if (up[u][e] != up[v][e]) {
            u = up[u][e];
            v = up[v][e];
        }
    }
    return up[u][0];
}

void dfs_pref(int u, int p = 0) {
    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);

    while (m--) {
        int s;
        cin >> s;
        vi q(s + 1);
        FOR(i, 0, s - 1) cin >> q[i];
        q[s] = q[0];
        FOR(i, 0, s - 1) {
            int u = q[i], v = q[i + 1];
            int x = lca(u, v);
            pref[u]++;
            pref[v]++;
            pref[x] -= 2;
        }
    }

    dfs_pref(1);

    vi res;
    FOR(i, 1, n - 1) {
        auto [u, v] = edges[i];
        if (depth[u] < depth[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();
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…