Submission #1218269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218269		3lektra	Railway (BOI17_railway)	C++20	0 / 100	1096 ms	21060 KiB

railway

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

const int maxN = 1e5+1;
const int lg = 17;

vector<pair<int,int>> graph[maxN]; // The graph.
int order[maxN]; // Just the nodes in the order they're visited
pair<int,int> range[maxN]; // When does it go in and when does it go out
int par[maxN][17]; // For the binary lifting
int depth[maxN]; // For finding the LCA
int edge[maxN]; // To know for each node which edge you have to go through
int req[maxN]; // The number of requests for each edge
bool semireq[maxN]; // Whether a track has been requested this round
int timer = 0; // To keep track of which iteration we are on
vector<int> rails; // To know what has each member requested and order it

//OK -- Order, Range, Binary Lifting
void dfs(int node){
    //cout << node << ' ' << timer << '\n';
    order[timer] = node;
    range[node].first = timer;
    for(pair<int,int> i : graph[node]){
        if(range[i.first].first == -1){
            timer++;
            par[i.first][0] = node;
            depth[i.first] = depth[node]+1;
            edge[i.first] = i.second;
            dfs(i.first);
        }
    }
    range[node].second = timer;
    for(int i = 1; i < lg; ++i){
        if(par[par[node][i-1]][i-1] == -1) break;
        par[node][i] = par[par[node][i-1]][i-1];
    }
}

/* Find the paths and update necessary edges
void mini_dfs(int u, int a){
    queue<int> tv;
    tv.push(a);
    int node;
    while(!tv.empty()){
        int node = tv.front();
        tv.pop();
        for(pair<int,int> i : graph[node]){

        }
    }

}
*/

// OK -- Find dth ancestor of u
int find_par(int u, int d){
    for(int i = lg-1; i >= 0; --i){
        if(d&(1<<i)) u = par[u][i];
    }
    return u;
}

// OK -- Find LCA
int lca(int u, int v, int n){
    if(depth[u] < depth[v]){ // swap
        u = u^v;
        v = u^v;
        u = u^v;
    }
    
    // Equalize depths
    u = find_par(u, (depth[u] - depth[v]));
    if(u == v) return u;
    //cout << u << ' ' << v << '\n';

    // Now Binary Search
    int maxi = n - depth[u];
    int mini = 0;
    int midi = mini + (maxi-mini)/2;
    int ans = 0;

    while(mini <= maxi){
        //cout << maxi << ' ' << mini << ' ' << midi << ' ' << ans << '\n';
        if(find_par(u, midi) != find_par(v, midi)){
            mini = midi+1;
        }
        else{
            //cout << "WAAAA " << find_par(u, midi) << '\n';
            ans = find_par(u, midi);
            maxi = midi-1;
        }
        midi = mini + (maxi-mini)/2;    
    }

    return ans;
}

// OK -- Order nodes
bool p_sort(int a, int b){
    return range[a].first > range[b].first;
}

int main(){
    int n, k, t, a, b;
    cin >> n >> t >> k;

    memset(graph, 0, sizeof(graph));
    memset(order, -1, sizeof(order));
    memset(range, -1, sizeof(range));
    memset(par, -1, sizeof(par));
    memset(depth, 0, sizeof(depth));
    memset(req, 0, sizeof(req));
    memset(edge, -1, sizeof(edge));

    // Reading and Preparing the Graph
    for(int i = 1; i < n; ++i){
        cin >> a >> b;
        a--; b--;
        graph[a].push_back({b,i});
        graph[b].push_back({a,i});
    }
    
    dfs(0);
    //cout << "-----------\n";
    //for(int i = 0; i < n; ++i) cout << order[i] << ' '; cout << '\n';
    //for(int i = 0; i < n; ++i) cout << edge[i] << ' '; cout << '\n';
    //for(int i = 0; i < n; ++i) cout << range[i].first << ' ' << range[i].second << '\n';

    //for(int i = 0; i < n; ++i) {for(int j = 0; j < lg; ++j){cout << par[i][j] << ' ';} cout << '\n';}


    // Computing queries
    while(t--){
        cin >> a;
        for(int i = 0; i < a; ++i) {cin >> b; b--; rails.push_back(b);}
        sort(rails.begin(), rails.end(), p_sort);
        for(int i = 0; i < a-1; ++i){
            b = lca(rails[i], rails[i+1], n);
            for(int j = range[b].first; j <= range[rails[i]].first; ++j){
                req[edge[order[j]]]++;
            }
            
        }
        rails.clear();
    }
    // Counting
    vector<int> ans;
    timer = 0;
    for(int i = 0; i < n; ++i){
        if(req[i] >= 2*k){
            ans.push_back(i);
            timer++;
        }
    }
    cout << timer << '\n';
    for(int i : ans) cout << i+1 << ' ';

    return 0;
}

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