Submission #473460

#	Time	Username	Problem	Language	Result	Execution time	Memory
473460		fadi57	Railway (BOI17_railway)	C++14	100 / 100	411 ms	66748 KiB

railway

#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+10;
typedef long long ll;

 int mod=1e9+7;
const int MXm=22;
#define F first
#define S second
const int inf=1e9+10;

vector<int>adj[mx];
 vector<pair<int,int>>edges;vector<int>ans;
  int n,m,k;
int depth[mx],dp[20][mx],sz[mx], active[mx];
  set<int>S[mx];
  vector<int>E[mx];
map<pair<int,int>,int>mp;

vector<int>vec[mx];

 void dfs(int node,int par){
 dp[0][node]=par;
 sz[node]=1;
for(int j=1;j<19;j++){

    dp[j][node]=dp[j-1][dp[j-1][node]];
}

  for(auto it:adj[node]){
     if(it==par){continue;}
     depth[it]=depth[node]+1;
     dfs(it,node);
    sz[node]+=sz[it];
  }
 return;
 }
 int kth(int node,int x){
  for(int i=0;i<19;i++){
   if(x&(1<<i)){
        x-=(1<<i);
        node=dp[i][node];
    }
 }
 return node;

 }
 int lca(int a,int b){

   if(depth[b]<depth[a]){swap(a,b);}
   int dis=depth[b]-depth[a];
    b=kth(b,dis);
  // cout<<b;
   if(a==b){return a;}

     for(int j=19;j>=0;j--){
   int aa=dp[j][a];int bb=dp[j][b];
  if(aa==bb){continue;}
  a=aa;b=bb;}

   return dp[0][a];

  }



  void dfs2(int node,int par,bool keep){
     int mx2=-1;int bigchild=-1;
   for(auto it:adj[node]){
     if(it==par){continue;}
    if(sz[it]>mx2){mx2=sz[it];bigchild=it;}
  }

   for(auto it:adj[node]){
    if(it!=bigchild&&it!=par){
        dfs2(it,node,0);
    }
   }
   if(bigchild!=-1){
    dfs2(bigchild,node,1);
    swap(S[bigchild],S[node]);
   }
 for(auto it:vec[node]){

    S[node].insert(it);
 }
   for(auto it:adj[node]){
    if(it!=bigchild&&it!=par){
        for(auto j:S[it]){

            S[node].insert(j);
        }
    }
    /*
    if(it!=par){
         if(vec[it].size()){mp[{min(it,node),max(it,node)}]++;}
    }
    */
   }
   for(auto it:E[node]){

    if(S[node].find(it)!=S[node].end()){
        S[node].erase(it);
    }
   }
  if(S[node].size()>=k){

  ans.push_back(mp[{node,par}]);

  }
return;
 }


 void test(){
 for(int i=1;i<=n;i++){

    for(int j=i+1;j<=n;j++){
        if(mp[{i,j}]){
            cout<<i<<" "<<j<<endl;
        }
    }
 }

 }

void test2(){


  cout<<ans.size()<<endl;
  sort(ans.begin(),ans.end());
  for(auto it:ans){
    cout<<it<<" ";
  }

 }

  int main(){
   ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
     cin>>n>>m>>k;
     for(int i=0;i<n-1;i++){
          int a,b;cin>>a>>b;

          mp[{a,b}]=mp[{b,a}]=i+1;
         edges.push_back({a,b});
          adj[a].push_back(b);
          adj[b].push_back(a);
      }
      dfs(1,0);
     for(int i=0;i<m;i++){

        int s;
        cin>>s;
        int now=0;
     for(int j=0;j<s;j++){
           int x;cin>>x;

           if(now==0){
                now=x;
           }else{
            now=lca(now,x);
           }
           active[i]=1;
         // S[x].insert(i);
          vec[x].push_back(i);
        }

     E[now].push_back(i);

      }
    dfs2(1,0,0);
      test2();
      }

Compilation message (stderr)

railway.cpp: In function 'void dfs2(int, int, bool)':
railway.cpp:106:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |   if(S[node].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