Submission #1299818

#TimeUsernameProblemLanguageResultExecution timeMemory
1299818onur8ocakRailway (BOI17_railway)C++20
0 / 100
149 ms44456 KiB
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pb push_back
#define all(v) v.begin(), v.end()
#define F first
#define S second

const int N = 100000;

int lift[N][21];
vector<int> adj[N], level(N,0), dep(N,0), v(N,0), ans;
map<pair<int,int>, int> E;
int cnt = 0, n, m, k;

void dfs(int node,int p){
    level[node] = cnt++;
    dep[node] = (p == -1 ? 0 : dep[p] + 1);   // ✔ FIX 1
    lift[node][0] = p;
    for(auto go : adj[node]){
        if(go != p) dfs(go, node);
    }
}

int dfsans(int node,int p){
    int sm = v[node];
    for(auto go : adj[node]){
        if(go != p) sm += dfsans(go, node);
    }
    if(p != -1 && sm / 2 >= k){               // ✔ FIX 3
        ans.pb(E[{min(node, p), max(node, p)}]);
    }
    return sm;
}

int LCA(int x,int y){
    if (dep[x] < dep[y]) swap(x,y);
    int diff = dep[x] - dep[y];
    for(int layer = 0; layer < 20; layer++){
        if(diff & (1LL << layer)) x = lift[x][layer];
    }
    if(x == y) return x;

    for(int layer = 19; layer >= 0; layer--){
        if(lift[x][layer] != lift[y][layer]){
            x = lift[x][layer];
            y = lift[y][layer];
        }
    }
    return lift[x][0];
}

void calclift(){
    for(int layer = 1; layer <= 19; layer++){
        for(int i = 0; i < n; i++){
            if (lift[i][layer-1] == -1) lift[i][layer] = -1;  // ✔ FIX 2
            else lift[i][layer] = lift[lift[i][layer-1]][layer-1];
        }
    }
}

void _(){
    cin >> n >> m >> k;

    for(int i = 1; i <= n - 1; i++){
        int u,vv;
        cin >> u >> vv;
        u--,vv--;
        adj[u].pb(vv);
        adj[vv].pb(u);
        E[{min(u, vv), max(u, vv)}] = i;
    }

    dfs(0, -1);
    calclift();

    while(m--){
        int siz;
        cin >> siz;
        deque<int> nodes;

        for(int i = 0; i < siz; i++){
            int x;
            cin >> x;
            x--;
            nodes.pb(x);
        }

        sort(all(nodes), [](int a, int b){
            return level[a] < level[b];
        });

        int lowest = nodes[0];
        for(int i = 1; i < siz; i++) lowest = LCA(lowest, nodes[i]);
        nodes.push_front(lowest);

        for(int i = 0; i < nodes.size(); i++){
            int anc = LCA(nodes[i], nodes[(i + 1) % nodes.size()]);
            v[anc] -= 2;
            v[nodes[i]] += 1;
            v[nodes[(i + 1) % nodes.size()]] += 1;
        }
    }

    dfsans(0, -1);

    cout << ans.size() << endl;
    for(auto pr : ans) cout << pr << " ";
    cout << endl;
}

int32_t main(){
    int t = 1;
    while(t--) _();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...