oj.uz

Submission #933493

# Submission time Handle Problem Language Result Execution time Memory
933493 2024-02-25T18:34:48 Z LucaIlie Railway (BOI17_railway) C++17
0 / 100
 1000 ms 21332 KB 
#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], parentEdge[MAX_N + 1];
edge edges[MAX_N];

int crt;
void dfs( int u, int p ) {
    timeIn[u] = ++crt;
    parent[0][u] = p;
    for ( int i = 1; (1 << i) <= 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] = crt;
}

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 ) {
    //printf( "%d %d: %d %d %d %d\n", u, v,  timeIn[u], timeOut[u], timeIn[v], timeOut[v] );
    return (timeIn[u] <= timeIn[v] && timeOut[v] <= timeOut[u]);
}

int k;
vector<int> ans;

int main() {
    int m;

    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() );

        /*for ( int v: virtualVertices )
            cout << v << " ";
        cout << "\n";*/
        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();

            //printf( "add %d %d\n", stack.back(), v );
            while ( v != stack.back() ) {
                used[v]++;
                v = parent[0][v];
            }

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

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

    cout << ans.size() << "\n";
    for ( int e: ans )
        cout << e << " ";

    return 0;
}

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1027 ms 21332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 19048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 19048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -