Submission #498623

#TimeUsernameProblemLanguageResultExecution timeMemory
498623JohannRailway (BOI17_railway)C++14
68 / 100
1040 ms65304 KiB
// 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, vpii & edges, int k) {
    int d = summe[in[v]] - summe[out[v]];
    if (d >= k) {
        if (v > p) edges.push_back({ p, v });
        else edges.push_back({ v, p });
    }

    for (int u : adj[v]) {
        if (u == p) continue;
        dfs2(adj, u, v, in, out, summe, edges, 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));
}

int lca(vvi & vorg, vi & depth, int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = lift(vorg, a, depth[a] - depth[b]);

    int low = 0; int up = depth[b];
    for (int mid = (up + low)/2; low < up; mid = (up + low)/2) {
        if (lift(vorg, a, mid) == lift(vorg, b, mid)) // gemeinsamer Vorgänger
            up = mid;
        else low = mid + 1;
    }
    return lift(vorg, b, low);
}

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,depth,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());
    vpii edges;
    dfs2(adj, 0, 0, in, out, summe, edges, k);
    sort(edges.begin(), edges.end());
    int v,u;
    cout << edges.size() << "\n";
    for (pii e : edges) {
        tie(v, u) = e;
        cout << mapping[{v,u}] << " ";
        // cout << ++v << " " << ++u << "\n";
    }

}


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++) {
      |                     ~~~~~~~~~~~^~~~~~~~~~~~~
#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...