Submission #940190

#	Time	Username	Problem	Language	Result	Execution time	Memory
940190		Pring	Railway (BOI17_railway)	C++17	100 / 100	97 ms	35784 KiB

railway

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
const string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << '[' << #x << "] : ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 100005;
int n, m, k, c, s[MXN];
int eu[MXN], ev[MXN];
vector<int> eid[MXN];

struct CLR {
    int clr[MXN], ans;
    void init(int n) {
        fill(clr + 1, clr + n + 1, 0);
        ans = 0;
    }
    void ADD(int a) {
        if (++clr[a] == 1) ans++;
    }
    void SUB(int a) {
        if (--clr[a] == 0) ans--;
    }
} clr;

namespace HLD {
    int d[MXN], p[MXN], sz[MXN], son[MXN], top[MXN], dfn[MXN], C;
    int rdfn[MXN], ep[MXN];
    vector<int> vc[MXN];

    void DFS1(int id, int par, int dep) {
        p[id] = par;
        d[id] = dep;
        sz[id] = 1;
        son[id] = -1;
        for (auto &e : eid[id]) {
            int i = eu[e] ^ ev[e] ^ id;
            if (i == par) continue;
            ep[i] = e;
            DFS1(i, id, dep + 1);
            sz[id] += sz[i];
            if (son[id] == -1) son[id] = i;
            else if (sz[son[id]] < sz[i]) son[id] = i;
        }
    }

    void DFS2(int id, int par, int _t) {
        top[id] = _t;
        rdfn[C] = id;
        dfn[id] = C++;
        if (son[id] != -1) DFS2(son[id], id, _t);
        for (auto &e : eid[id]) {
            int i = eu[e] ^ ev[e] ^ id;
            if (i == par) continue;
            if (i == son[id]) continue;
            DFS2(i, id, i);
        }
    }

    void DO(int rt) {
        DFS1(1, 0, 0);
        DFS2(1, 0, 1);
    }

    void ADD(int x, int y, int c) {
        while (top[x] != top[y]) {
            if (d[top[x]] < d[top[y]]) swap(x, y);
            vc[dfn[top[x]]].push_back(c);
            vc[dfn[x] + 1].push_back(-c);
            x = p[top[x]];
        }
        if (d[x] < d[y]) swap(x, y);
        vc[dfn[y] + 1].push_back(c);
        vc[dfn[x] + 1].push_back(-c);
    }

    void BOX(vector<int> &v, int k) {
        clr.init(m);
        FOR(i, 0, n) {
            for (auto &j : vc[i]) {
                if (j > 0) clr.ADD(j);
                else clr.SUB(-j);
            }
            if (clr.ans >= k) v.push_back(ep[rdfn[i]]);
        }
    }
}

void miku() {
    cin >> n >> m >> k;
    FOR(i, 1, n) {
        cin >> eu[i] >> ev[i];
        eid[eu[i]].push_back(i);
        eid[ev[i]].push_back(i);
    }
    HLD::DO(1);
    FOR(j, 1, m + 1) {
        cin >> c;
        FOR(i, 0, c) cin >> s[i];
        FOR(i, 1, c) HLD::ADD(s[0], s[i], j);
    }
    vector<int> ans;
    HLD::BOX(ans, k);
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (auto &i : ans) cout << i << ' ';
    cout << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    miku();
    return 0;
}

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