제출 #1163748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163748		ChottuF	Railway (BOI17_railway)	C++20	29 / 100	192 ms	46888 KiB

railway

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


/*
this is the idea

-> keep joining from smallest depth to biggest depth and replace with LCA
   this will ensure the S^2 contiguous segment of tree is now just S log N
   keep popping smallest 2 depths and replace with LCA
   
   +1 on starting and -2 on parent of LCA
   
   but we run into duplication problem, where we might overcount since the procedure is
   not monotonic wrt depth, so we will use add and remove sets on nodes
   
   so imagine like merging from leaf to roots, and using small to large merging will speed
   this up so it can actually work!! this is probably overkill and not intended but 100pts is 100pts
   
   use map as it is more memory efficient and multiset is very not memory efficient
*/

const int MAXN = 1e5+5;
const int MAXH = 22;

vector<vector<int>> adj;

int up[MAXH][MAXN];
int depth[MAXN];

void dfs(int x, int p, int d){
    depth[x] = d;
    up[0][x] = p;
    for (auto u : adj[x]){
        if (u == p) continue;
        dfs(u,x,d+1);
    }
}

int jmp(int x, int k){
    for (int i = 0; i<MAXH; i++){
        if (k & (1 << i)){
            x = up[i][x];
        }
    }
    return x;
}

int lca(int a, int b){
    if (depth[a] < depth[b]) swap(a,b);
    a = jmp(a, depth[a]-depth[b]);
    if (a == b) return a;
    for (int i = MAXH-1; i>=0; i--){
        if (up[i][a] != up[i][b]){
            a = up[i][a];
            b = up[i][b];
        }
    }
    return up[0][a];
}

map<int,int> tree[MAXN];
int ans[MAXN];
void dfs2(int x, int p){
    for (auto u : adj[x]){
        if (u == p) continue;
        dfs2(u,x);
        if (tree[x].size() < tree[u].size()) swap(tree[x],tree[u]);
        for (auto d : tree[u]){
            auto [one,two] = d;
            tree[x][one] += two;
            if (tree[x][one] == 0) tree[x].erase(one);
        }
    }
    ans[x] = tree[x].size();
}

int main(){
    int n,m,k;
    cin >> n >> m >> k;
    adj.resize(n+1);
    map<pair<int,int>,int> mpp;
    for (int i = 0; i<n-1; i++){
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        if (a > b) swap(a,b);
        mpp[{a,b}] = i+1;
    }
    dfs(1,0,1);
    for (int j = 1; j<MAXH; j++){
        for (int i = 1; i<=n; i++){
            up[j][i] = up[j-1][up[j-1][i]];
        }
    }
    for (int dd = 0; dd<m; dd++){
        int s;
        cin >> s;
        set<int> all;
        for (int i = 0; i<s; i++){
            int x;
            cin >> x;
            all.insert(x);
        }
        while (all.size() >= 2){
            auto it = all.begin(); int one = *it; all.erase(it);
            it = all.begin(); int two = *it; all.erase(it);
            if (depth[one] > depth[two]) swap(one,two);
            int three = lca(one,two);
            if (one == three){
                tree[one][dd]--;
                tree[two][dd]++;
            }
            else{
                tree[one][dd]++;
                tree[two][dd]++;
                tree[three][dd]-=2;
                all.insert(three);
                
            }
        }
    }
    dfs2(1,0);
    vector<int> qqq;
    for (int i = 1; i<=n; i++){
        if (ans[i] >= k){
            int one = i;
            int two = up[0][i];
            if (one > two) swap(one,two);
            qqq.push_back(mpp[{one,two}]);
        }
    }
    sort(qqq.begin(),qqq.end());
    cout << qqq.size() << '\n';
    for (auto u : qqq){
        cout << u << " ";
    }
    return 0;
}

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