제출 #1222857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222857		zyadhany	Railway (BOI17_railway)	C++20	100 / 100	215 ms	102064 KiB

railway

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
 
#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define vi vector<ll>
#define vii vector<vi>
#define viii vector<vii>
#define vc vector<char>
#define vcc vector<vc>
#define vp vector<pl>
#define mi map<ll,ll>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define all(X) X.begin(),X.end()
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}
using namespace std;
 
const int MODE = 1e9+7;

class Graph {
public:
    int size, SPSIZE;
    vi Indeg, lvl;
    vp Trav;
    vector<vp> table;
    vi dp;

    void dfs( const vii &adj, int n, int p, ll deep) {
        lvl[n] = deep;
        Indeg[n] = Trav.size();
        Trav.push_back({deep, n});
        for (auto neg : adj[n]) {
            if (neg == p) continue;
            dfs(adj, neg, n, deep + 1);
            Trav.push_back({deep, n});
        }
    }

    void BuildLCA() {
        ll n = Trav.size();
        SPSIZE = ceil(log2(n));
        table.resize(n, vp(SPSIZE + 1));
        for (int i = 0; i < n; i++)
            table[i][0] = Trav[i];
        
        for (int j = 1; j <= SPSIZE; j++)
            for (int i = 0; i <= n - (1 << j); i++)
                table[i][j] = min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
    }

    ll LCA(ll a, ll b) {
        ll l = Indeg[a], r = Indeg[b];
        if (l > r) swap(l, r);
        int j = (int)log2(r - l + 1); 
        return min(table[l][j], table[r - (1 << j) + 1][j]).second;
    }

    ll dist(ll a, ll b) {
        return lvl[a] + lvl[b] - 2 * lvl[LCA(a, b)];
    }

    vector<vp> virtual_tree(vi &nodes) {
        // compare in dfs order
        auto cmp = [&](ll a, ll b) {
            return Indeg[a] < Indeg[b];
        };
        sort(all(nodes), cmp);
        ll n = nodes.size();
        for (int i = 0; i < n-1; i++)
        {
            nodes.push_back(LCA(nodes[i], nodes[i+1]));
        }

        sort(all(nodes), cmp);
        nodes.erase(unique(all(nodes)), nodes.end());        
        n = nodes.size();

        vector<vp> adj(n);
        stack<ll> st;
        st.push(0);
        for (int i = 1; i < n; i++)
        {
            while (LCA(nodes[st.top()], nodes[i]) != nodes[st.top()]) st.pop();
            adj[st.top()].push_back({i, dist(nodes[st.top()], nodes[i])});
            st.push(i);
        }
        
        return adj;
    }

    ll dfsquery(vector<vp> &adj, vi &V, ll n) {
        ll cnt = 0;
        for (auto [neg, w] : adj[n]) {
            cnt += dfsquery(adj, V, neg);
        }

        if (!cnt) {
            dp[V[n]]++;
        } else {
            dp[V[n]] += 1 - cnt;
        }
        return 1;
    }

    void query(vi nodes) {
        set<ll> st(all(nodes));
        auto adj = virtual_tree(nodes);
        ll n = nodes.size();
        dfsquery(adj, nodes, 0);
        dp[nodes[0]]--;
    }

    Graph(ll n, const vii &adj) : size(n), lvl(n+1), Indeg(n+1), dp(n+1) {
        dfs(adj, 1, 0, 1);
        BuildLCA();
    }
};

void req(vector<vp> &adj, vi &res, vi &dp, ll n, ll ed, ll k) {
    for (auto [neg, ind] : adj[n]) if (ind != ed) {
        req(adj, res, dp, neg, ind, k);
        if (dp[neg] >= k) res.push_back(ind);
        dp[n] += dp[neg];
    }
}

void solve(int tc) {
    ll n, m, k;

    cin >> n >> m >> k;

    vii adj(n + 1);
    vector<vp> adjw(n + 1);
    for (int i = 0; i < n-1; i++)
    {
        ll u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        adjw[u].push_back({v, i+1});
        adjw[v].push_back({u, i+1});
    }
    
    Graph gr(n, adj);

    while (m--)
    {
        ll s; cin >> s;
        vi nd(s);
        for (int i = 0; i < s; i++)
            cin >> nd[i];
        gr.query(nd);
    }
    
    vi res;

    req(adjw, res, gr.dp, 1, 0, k);

    sortx(res);
    cout << res.size() << '\n';
    for (auto a : res) cout << a << ' ';
    cout << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int size = 1;    
 
	// freopen("gathering.in", "r", stdin);
    // freopen("gathering.out", "w", stdout);
 
    // cin >> size;
    for (int i = 1; i <= size ; i++) solve(i);
    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