Submission #472268

#	Time	Username	Problem	Language	Result	Execution time	Memory
472268		fadi57	Railway (BOI17_railway)	C++14	8 / 100	1089 ms	31972 KiB

railway

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const int mx=1e5+5;
typedef long long ll;
 int mod=1e9+7;
const int MXm=22;
#define F first
#define S second
const int inf=1e9+10;
int aa[mx];
vector<int>adj[mx];
vector<pair<int,int>>edges;
int depth[mx];
int dp[20][mx];
int dp2[mx];
void dfs(int node,int par){
 
 dp[0][node]=par;
 
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);
 
 
 }
 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];
 
  }
 
int n,m,k;
map<pair<int,int>,int>mp;
int dfs2(int node,int par){
 
 int sum2=0;
  for(auto it:adj[node]){
     if(it==par){continue;}
 
    int z= dfs2(it,node);
   if(z>0){
    int x=min(node,it);int y=max(node,it);
     mp[{x,y}]++;
 
   }
   sum2+=z;
 
 }
 dp2[node]+=sum2;
 //cout<<node<<" "<<dp2[node]<<endl;
 return dp2[node];
 
 }
 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(){
 
vector<int>ans;
int anss=0;
 for(int i=0;i<n;i++){
 if(mp[{edges[i].first,edges[i].second}]>=k){
    anss++;
    ans.push_back(i+1);
}
 
 }
 cout<<anss<<endl;
 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;
          if(b<a){swap(a,b);}
          edges.push_back({a,b});
          adj[a].push_back(b);
          adj[b].push_back(a);
      }
      dfs(1,0);
    //  cout<<lca(3,1);
 
      for(int i=0;i<m;i++){
        memset(dp2,0,sizeof(dp2));
        int s;cin>>s;
 
        int a[s];
        for(int j=0;j<s;j++){
            cin>>a[j];
        }
        for(int j=0;j<s;j++){
            for(int jj=j+1;jj<s;jj++){
                int me=lca(a[j],a[jj]);
                dp2[me]-=2;
                dp2[a[j]]++; dp2[a[jj]]++;
              //  cout<<me<<endl;
            }
        }
        dfs2(1,0);
 // test();
  //mp.clear();
     //   cout<<"test \n";
      }
      test2();
 
      /*
      cout<<dp[1][6];
        lca(6,5);
*/
 
 
 
 
 
    }
    /*
 7 5 5
 1 2
 1 3
 3 5
 3 4
 4 7
 4 6
*/

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