Submission #498627

#	Time	Username	Problem	Language	Result	Execution time	Memory
498627		Johann	Railway (BOI17_railway)	C++14	100 / 100	243 ms	65588 KiB

railway

// https://oj.uz/problem/view/BOI17_railway

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

#define ll long long
#define pii pair<int, int>
#define tiii tuple<int,int,int>
#define vi vector<ll>
#define vvi vector<vi>
#define vpii vector<pii>
#define vtiii vector<tiii>


void dfs(vvi & adj, int v, int p, vi & in, vi & out, vvi & vorg, int & cnt, vi & depth, int d) {
    in[v] = cnt++;
    vorg[v].push_back(p); // erster vorg
    for (int i = 1; 1 << (i-1) < vorg.size(); i++) {
        vorg[v].push_back(vorg[vorg[v][i-1]][i-1]);
    }
    depth[v] = d;

    for (int u : adj[v]) {
        if (u == p) continue;
        dfs(adj, u, v, in, out, vorg, cnt, depth, d+1);
    }

    out[v] = cnt++;
}

void dfs2(vvi & adj, int v, int p, vi & in, vi & out, vi & summe, vi & edges, map<pii,int> & mapping, int k) {
    int d = summe[in[v]] - summe[out[v]];
    if (d >= k) {
        if (v > p) edges.push_back(mapping[{ p, v }]);
        else edges.push_back(mapping[{ v, p }]);
    }

    for (int u : adj[v]) {
        if (u == p) continue;
        dfs2(adj, u, v, in, out, summe, edges, mapping, k);
    }
}

int lift(vvi & vorg, int a, int k) {
    if (k == 0) return a;
    int i = floor(log2(k));
    return lift(vorg, vorg[a][i], k - (1 << i));
}

bool is_predecessor(int u, int v, vi & in, vi & out) { // u Vorgänger von v
    return in[u] <= in[v] && out[u] >= out[v];
}

int lca(vvi & vorg, vi & in, vi & out, int u, int v) {
    if (is_predecessor(u,v,in,out)) return u;
    if (is_predecessor(v,u,in,out)) return v;

    for (int i = vorg[0].size(); i >= 0; --i) {
        if (!is_predecessor(vorg[u][i], v, in, out))
            u = vorg[u][i];
    }
    return vorg[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    map<pii, int> mapping;
    int n,m,k;
    cin >> n >> m >> k;
    vvi adj(n);
    for (int i = 1,a,b; i < n; i++) {
        cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
        if (a > b) swap(a,b);
        mapping[make_pair(a,b)] = i;
    }

    // root = 0;
    vi in(n);
    vi out(n);
    vi depth(n);
    vvi vorg(n);
    int cnt = 0;
    dfs(adj, 0, 0, in, out, vorg, cnt, depth, 0);
    vi pref(2 * n);

    for (int i = 0,s; i < m; i++) {
        cin >> s;
        vpii neighbors(s);
        for (int j = 0,l; j < s; j++) {
            cin >> l; l--;
            neighbors[j] = make_pair( in[l], l );
        }
        sort(neighbors.begin(), neighbors.end());
        int current_lca = neighbors[0].second; // der lca aller bisher betrachteten Knoten
        for (int j = 1; j < s; j++) {
            int v = neighbors[j-1].second;
            int u = neighbors[j].second;
            int l = lca(vorg,in,out,v,u);
            if (in[l] < in[current_lca]) {
                // hier ist der current lca unter dem aktuellen lca
                pref[in[l]+1]++;
                pref[in[current_lca]+1]--;
                pref[in[l]+1]++;
                pref[in[u]+1]--;
                current_lca = l;
            } else {
                // hier ist der gefunden lca unter dem akutellen lca
                pref[in[l]+1]++;
                pref[in[u]+1]--;
            }
        }
    }

    vi summe(2 * n + 1);
    partial_sum(pref.begin(), pref.end(), summe.begin());
    vi edges;
    dfs2(adj, 0, 0, in, out, summe, edges, mapping, k);
    sort(edges.begin(), edges.end());
    cout << edges.size() << "\n";
    for (int e : edges) {
        cout << e << " ";
    }

}

Compilation message (stderr)

railway.cpp: In function 'void dfs(std::vector<std::vector<long long int> >&, int, int, std::vector<long long int>&, std::vector<long long int>&, std::vector<std::vector<long long int> >&, int&, std::vector<long long int>&, int)':
railway.cpp:18:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 1; 1 << (i-1) < vorg.size(); i++) {
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~

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