Submission #472261

#	Time	Username	Problem	Language	Result	Execution time	Memory
472261		fadi57	Railway (BOI17_railway)	C++14	8 / 100	1092 ms	34656 KiB

railway

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const int mx=2e5+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(){


       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