Submission #1219944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219944		lopkus	Railway (BOI17_railway)	C++20	100 / 100	84 ms	22716 KiB

railway

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")

//Andrew Holod will NOT win IOI 2025
//Andrew Holod did not qualify to IOI 2025))))))))))
//Anton is nigga

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cstring> // Для memset

using namespace std;

typedef long long ll;
typedef long double ld;
typedef std::pair <ll, ll> pii;
typedef std::pair <ld, ld> pdd;

const ll DIM = 100007;
const ll MXMASK = (1 << 20);
const ll INF = 1e18;
const ll mod = 1000000007;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;
const char endL = '\n';

const ll dx[4] = { 1, 0, -1, 0 };
const ll dy[4] = { 0, 1, 0, -1 };

FILE* stream;

int n, m, k;
vector < pair < int, int > > v[DIM];

int timer;
int euler[DIM], tin[DIM], tout[DIM], heavy[DIM], weight[DIM], depth[DIM];

vector < int > colors[DIM];

vector < int > res;

void precount(int val, int prev, int dep) {
    tin[val] = ++timer;
    euler[timer] = val;

    depth[val] = dep;

    weight[val] = 1;
    for (auto e : v[val]) {
        int to = e.first;

        if (to == prev) continue;
        precount(to, val, dep + 1);
        weight[val] += weight[to];
    }

    tout[val] = timer;
}

int cnt[DIM], fullColor[DIM];
int ans;

void add(int col) {
    if (cnt[col] == 0) ans++;
    cnt[col]++;
    if (cnt[col] == fullColor[col]) ans--;
}

void del(int col) {
    if (cnt[col] == fullColor[col]) ans++;
    cnt[col]--;
    if (cnt[col] == 0) ans--;
}

void solve(int val, int prev, bool heavyStat) {
    int heavy = 0, heavyE = 0;

    for (auto e : v[val]) {
        int to = e.first, num = e.second;
        if (num == prev) continue;
        if (weight[to] > weight[heavy]) {
            heavy = to;
            heavyE = num;
        }
    }

    for (auto e : v[val]) {
        int to = e.first, num = e.second;
        if (to != heavy && num != prev) {
            solve(to, num, false);
        }
    }

    if (heavy != 0) {
        solve(heavy, heavyE, true);
    }

    for (auto e : v[val]) {
        int to = e.first, num = e.second;
        if (to != heavy && num != prev) {
            for (int i = tin[to]; i <= tout[to]; i++) {
                for (auto x : colors[euler[i]]) {
                    add(x);
                }
            }
        }
    }

    for (auto x : colors[val]) {
        add(x);
    }

    if (ans >= k && prev != -1) res.push_back(prev);

    if (!heavyStat) {
        for (int i = tin[val]; i <= tout[val]; i++) {
            for (auto x : colors[euler[i]]) {
                del(x);
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

    //freopen_s(&stream, "input.txt", "r", stdin);
    //freopen_s(&stream, "output.txt", "w", stdout);    

    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        v[v1].push_back({ v2, i });
        v[v2].push_back({ v1, i });
    }
    
    precount(1, 1, 1);

    for (int i = 1; i <= m; i++) {
        int x;
        cin >> fullColor[i];
        for (int j = 1; j <= fullColor[i]; j++) {
            cin >> x;
            colors[x].push_back(i);
        }
    }

    solve(1, -1, true);

    cout << res.size() << endl;
    sort(res.begin(), res.end());
    for (auto x : res) cout << x << " ";

    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