Submission #933499

#	Time	Username	Problem	Language	Result	Execution time	Memory
933499		LucaIlie	Railway (BOI17_railway)	C++17	100 / 100	118 ms	26060 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int MAX_LOG_N = 16;

struct edge {
    int u, v;
};

int n;
vector<int> adj[MAX_N + 1];
int parent[MAX_LOG_N + 1][MAX_N + 1], depth[MAX_N + 1], timeIn[MAX_N + 1], timeOut[MAX_N + 1], used[MAX_N + 1], parentEdge[MAX_N + 1];
edge edges[MAX_N];

int timee;
void dfs( int u, int p ) {
    timeIn[u] = ++timee;
    parent[0][u] = p;
    for ( int i = 1; i <= log2( n ); i++ )
        parent[i][u] = parent[i - 1][parent[i - 1][u]];
    depth[u] = depth[p] + 1;
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
    timeOut[u] = ++timee;
}

int lca( int u, int v ) {
    if ( depth[u] < depth[v] )
        swap( u, v );

    for ( int p = log2( n ); p >= 0; p-- ) {
        if ( depth[parent[p][u]] >= depth[v] )
            u = parent[p][u];
    }

    if ( u == v )
        return u;

    for ( int p = log2( n ); p >= 0; p-- ) {
        if ( parent[p][u] != parent[p][v] ) {
            u = parent[p][u];
            v = parent[p][v];
        }
    }

    return parent[0][u];
}

bool inSubtree( int u, int v ) {
    return (timeIn[u] <= timeIn[v] && timeOut[v] <= timeOut[u]);
}

vector<int> ans;

void getUsed( int u, int p ) {
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        getUsed( v, u );
        used[u] += used[v];
    }
}

int main() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );

    int m, k;

    cin >> n >> m >> k;
    for ( int i = 1; i < n; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
        edges[i] = { u, v };
    }

    dfs( 1, 0 );

    for ( int i = 1; i < n; i++ ) {
        if ( depth[edges[i].u] > depth[edges[i].v] )
            swap( edges[i].u, edges[i].v );
        parentEdge[edges[i].v] = i;
    }

    for ( int i = 0; i < m; i++ ) {
        int s;
        cin >> s;

        vector <int> vertices, virtualVertices;
        for ( int j = 0; j < s; j++ ) {
            int v;
            cin >> v;
            vertices.push_back( v );
            virtualVertices.push_back( v );
        }
        sort( vertices.begin(), vertices.end(), []( int u, int v ) {
            return timeIn[u] < timeIn[v];
        } );
        for ( int j = 0; j < s - 1; j++ )
            virtualVertices.push_back( lca( vertices[j], vertices[j + 1] ) );
        sort( virtualVertices.begin(), virtualVertices.end(), []( int u, int v ) {
            return timeIn[u] < timeIn[v];
        } );
        virtualVertices.resize( unique( virtualVertices.begin(), virtualVertices.end() ) - virtualVertices.begin() );

        vector <int> stack;
        stack.push_back( virtualVertices[0] );
        for ( int j = 1; j < virtualVertices.size(); j++ ) {
            int v = virtualVertices[j];

            while ( !inSubtree( stack.back(), v ) )
                stack.pop_back();

            used[stack.back()]--;
            used[v]++;

            stack.push_back( virtualVertices[j] );
        }
    }

    getUsed( 1, 0 );

    for ( int v = 1; v <= n; v++ ) {
        if ( used[v] >= k )
            ans.push_back( parentEdge[v] );
    }

    cout << ans.size() << "\n";
    sort( ans.begin(), ans.end() );
    for ( int e: ans )
        cout << e << " ";

    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:115:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for ( int j = 1; j < virtualVertices.size(); j++ ) {
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~

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