Submission #472327

#	Time	Username	Problem	Language	Result	Execution time	Memory
472327		fadi57	Railway (BOI17_railway)	C++14	8 / 100	1093 ms	36932 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];
 vector<int>a[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<<" ";
 }

 }
 void solve(){
     for(int i=0;i<m;i++){
      int me=lca(a[i][0],a[i][1]);
     dp2[me]-=2;
    dp2[a[i][0]]++; dp2[a[i][1]]++;


        }
        dfs2(1,0);
        }




       void solve2(){
     for(int i=0;i<m;i++){
            memset(dp2,0,sizeof(dp2));
               for(int j=0;j<a[i].size();j++){
               for(int jj=j+1;jj<a[i].size();jj++){
                 int me=lca(a[i][j],a[i][jj]);
                 dp2[me]-=2;
                 dp2[a[i][j]]++; dp2[a[i][jj]]++;
              //  cout<<me<<endl;
            }
        }
        dfs2(1,0);


        }

        }









 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);
      }
      int leaf1=0;int leaf2=0;
      dfs(1,0);
      int ok=0; int ok2=1;

      for(int i=0;i<m;i++){

        int s;cin>>s;
       for(int j=0;j<s;j++){
           int x;cin>>x;
           a[i].push_back(x);
        }

        if(k==m&&s==2){

        }else{

        ok=0;
       }

 // test();
  //mp.clear();
     //   cout<<"test \n";
      }
      if(ok){
       solve();
      }else{
      solve2();
      }
      test2();

      /*
      cout<<dp[1][6];
        lca(6,5);
*/

}

Compilation message (stderr)

railway.cpp: In function 'void solve2()':
railway.cpp:138:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |                for(int j=0;j<a[i].size();j++){
      |                            ~^~~~~~~~~~~~
railway.cpp:139:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |                for(int jj=j+1;jj<a[i].size();jj++){
      |                               ~~^~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:173:11: warning: unused variable 'leaf1' [-Wunused-variable]
  173 |       int leaf1=0;int leaf2=0;
      |           ^~~~~
railway.cpp:173:23: warning: unused variable 'leaf2' [-Wunused-variable]
  173 |       int leaf1=0;int leaf2=0;
      |                       ^~~~~
railway.cpp:175:21: warning: unused variable 'ok2' [-Wunused-variable]
  175 |       int ok=0; int ok2=1;
      |                     ^~~

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