제출 #390915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390915		Victor	Railway (BOI17_railway)	C++17	23 / 100	1090 ms	14264 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

int n, m, k, cnt[100001], layer[100001], curr;
vii graph[100001];

bool dfs(int u, int p) {
    bool ret = (layer[u] == curr);
    trav(edge, graph[u]) if (edge.first != p) {
        if (dfs(edge.first, u)) ++cnt[edge.second], ret = 1;
    }
    return ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    memset(cnt, 0, sizeof(cnt));
    memset(layer, -1, sizeof(layer));
    cin >> n >> m >> k;
    int a, b;
    rep(i, 0, n - 1) {
        cin >> a >> b;
        graph[--a].emplace_back(--b, i);
        graph[b].emplace_back(a, i);
    }
    
    rep(i, 0, m) {
        int s, u;
        curr = i;
        cin >> s;
        rep(j, 0, s) cin >> u, layer[u - 1] = i;
        dfs(u - 1, u - 1);
    }

    vi ans;
    rep(i, 0, n) {
        if (k <= cnt[i]) ans.pb(i + 1);
    }

    cout << sz(ans) << endl;
    trav(edge, ans) cout << edge << ' ';
    cout << endl;
    return 0;
}

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