Submission #964089

#	Time	Username	Problem	Language	Result	Execution time	Memory
964089		Aiperiii	Railway (BOI17_railway)	C++14	100 / 100	347 ms	61224 KiB

railway

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <int > g[N];
set <int> st1[N],st2[N];
int jmp[20][N];
int d[N];
map <pair <int,int> ,int> mp;
int n,m,k;
void dfs(int v,int p){
    jmp[0][v]=p;
    for(auto to : g[v]){
        if(to!=p){
            d[to]=d[v]+1;
            dfs(to,v);
        }
    }
}
int lca(int v,int u){
    if(d[u]<d[v])swap(u,v);
    for(int i=19;i>=0;i--){
        if(d[jmp[i][u]]>=d[v]){
            u=jmp[i][u];
        }
    }
    if(u==v)return v;
    for(int i=19;i>=0;i--){
        if(jmp[i][u]!=jmp[i][v]){
            u=jmp[i][u];
            v=jmp[i][v];
        }
    }
    return jmp[0][v];
}
vector <int> ans;
void calc(int v,int p){
    int mx=st1[v].size();
    int node=v;
    for(auto to : g[v]){
        if(to!=p){
            calc(to,v);
            if(st1[to].size()>mx){
                mx=st1[to].size();
                node=to;
            }
        }
    }
    swap(st1[v],st1[node]);
    for(auto to : g[v]){
        if(to!=p){
            for(auto x : st1[to])st1[v].insert(x);
            st1[to].clear();
        }
    }
    for(auto x : st2[v])st1[v].erase(x);
    if(st1[v].size()>=k){
        ans.pb(v);
    }
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        mp[{u,v}]=i;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,1);
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            jmp[i][j]=jmp[i-1][jmp[i-1][j]];
        }
    }
    for(int i=1;i<=m;i++){
        int s;
        cin>>s;
        int p=0;
        for(int j=0;j<s;j++){
            int x;
            cin>>x;
            if(p==0)p=x;
            else {
                p=lca(p,x);
            }
            st1[x].insert(i);
        }
        st2[p].insert(i);
    }
    calc(1,0);
    vector <int> res;
    for(auto x : ans){
        if(mp[{x,jmp[0][x]}])res.pb(mp[{x,jmp[0][x]}]);
        else res.pb(mp[{jmp[0][x],x}]);
    }
    sort(all(res));
    cout<<res.size()<<"\n";
    for(auto x : res)cout<<x<<" ";
}

/*
6 3 2
1 3
2 3
3 4
6 4
4 5
4 1 3 2 5
2 6 3
2 3 2
 
*/

Compilation message (stderr)

railway.cpp: In function 'void calc(long long int, long long int)':
railway.cpp:47:30: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   47 |             if(st1[to].size()>mx){
      |                ~~~~~~~~~~~~~~^~~
railway.cpp:61:21: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   61 |     if(st1[v].size()>=k){
      |        ~~~~~~~~~~~~~^~~

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