제출 #1172305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172305		crafticat	Railway (BOI17_railway)	C++20	100 / 100	270 ms	52860 KiB

railway

#include <bits/stdc++.h>

using namespace std;


#define F0R(i, n) for (int i= 0 ; i< n;i++)
#define FOR(i,j,n) for (int i = j; i< n;i++)

template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;

vi buffer;

struct STL
{
    V<map<int, int>> maps;
    vi id;

    STL(int n) {
        maps.resize(n), id.resize(n);
        F0R(i, n)
            id[i] = i;
    }

    void add(int x, int col) {
        maps[id[x]][col]++;
        if (maps[id[x]][col] == buffer[col])
            maps[id[x]].erase(col);
    }

    void combine(int a, int b) {
        int orgA = a, orgB = b;
        a = id[a], b = id[b];

        // B is small
        if (maps[b].size() > maps[a].size())
            swap(a,b);

        for (auto [col, app] : maps[b]) {
            maps[a][col] += app;

            if (maps[a][col] == buffer[col])
                maps[a].erase(col);
        }
        id[orgA] = id[orgB] = a;
    }
    int siz(int x) {
        return maps[id[x]].size();
    }
};

V<vi> colors;
V<vi> g;
STL* stl;
map<pi, int> edgeID;
vi ans;
int k;

void dfs(int x, int p) {
    for (auto c : colors[x])
        stl->add(x, c);

    for (auto y : g[x]) {
        if (y == p) continue;
        dfs(y, x);
        stl->combine(x, y);
    }

    if (p != -1 and stl->siz(x) >= k)
        ans.push_back(edgeID[{x,p}]);
}

int main() {
    int n, m; cin >> n >> m >> k;

    g.resize(n + 1), colors.resize(n + 1), buffer.resize(m);
    F0R(i, n - 1) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        edgeID[{a,b}] = i;
        edgeID[{b,a}] = i;
    }

    F0R(i, m) {
        int d; cin >> d;
        buffer[i] = d;

        F0R(j, d) {
            int x; cin >> x;
            colors[x].push_back(i);
        }
    }

    stl = new STL(m + n + 1);
    dfs(1, -1);

    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (auto x : ans) {
        cout << x + 1 << " ";
    }
}

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