Submission #633103

#	Time	Username	Problem	Language	Result	Execution time	Memory
633103		no_namee	Railway (BOI17_railway)	C++14	100 / 100	288 ms	58984 KiB

railway

#include<bits/stdc++.h>
#define down '\n'
#define lli long long int
#define ulli unsigned long long int
#define ld long double
using namespace std;

const int maxn = 1e5+100;
const int LOGG = 19;

int n,m,k, high[maxn], lca[maxn][LOGG];
bool check[maxn];
vector<int> adj[maxn], removee[maxn] , ans;
map< pair<int,int> , int > save;
set<int> save2[maxn];

void dfs( int u, int p)
{
    lca[u][0] = p;
    high[u] = high[p] + 1;
    for( int i = 1; i < LOGG ; i ++ ) lca[u][i] = lca[ lca[u][i-1] ][i-1];
    for( int v : adj[u] )
    {
        if( v != p ) dfs( v,u );
    }
}
void dfs2( int u , int p )
{
    for( int v : adj[u] )
    {
        if( v != p )
        {
            dfs2( v, u );
            if( save2[v].size() >  save2[u].size() ) save2[u].swap( save2[v] );
            save2[u].insert( save2[v].begin() , save2[v].end() );
            save2[v].clear();
        }
    }
    for( int v : removee[u] )save2[u].erase(v);
    if( save2[u].size() >= k) check[u] = true;

}
int find_lca( int u, int v )
{
    if( high[u] < high[v] ) swap(u,v);
    int differ = high[u] - high[v];
    for( int i = LOGG - 1; i >= 0; i -- )
    {
        if( ((differ>>i)&1) ) u = lca[u][i];
    }
    if( u ==  v ) return u;
    for( int i = LOGG- 1; i >= 0 ; i -- )
    {
        if( lca[u][i] != lca[v][i] )
        {
            u = lca[u][i];
            v = lca[v][i];
        }
    }
    return lca[u][0];
}
void read()
{
    cin >> n >> m >> k;
    int u,v;
    for( int i = 1; i < n; i ++ )
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        save[ {u,v} ] =  save[ {v,u} ] = i;
    }
    dfs(1,1);
}
void solve()
{
    int s,lowest_common_ancestor,  vertex;
    for( int idx = 1;  idx <= m ; idx ++ )
    {
        cin >> s >> vertex;
        lowest_common_ancestor = vertex;
        save2[vertex].insert(idx);
        for( int i = 1; i < s;  i ++ )
        {
            cin >> vertex;
            save2[vertex].insert(idx);
            lowest_common_ancestor = find_lca( lowest_common_ancestor, vertex );
        }
        removee[lowest_common_ancestor].push_back( idx );
    }
    dfs2(1,1);
    for( int i = 2; i <= n; i ++ )
    {
        if( check[i] ) ans.push_back( save[ {i, lca[i][0] } ] );
    }
    sort( ans.begin() , ans.end() );
    cout << ans.size() << down;
    for( int vertex  : ans ) cout << vertex <<" ";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read();
    solve();
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs2(int, int)':
railway.cpp:40:25: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if( save2[u].size() >= k) check[u] = true;
      |         ~~~~~~~~~~~~~~~~^~~~

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