Submission #534969

# Submission time Handle Problem Language Result Execution time Memory
534969 2022-03-09T08:10:20 Z almothana05 Tropical Garden (IOI11_garden) C++17
0 / 100
164 ms 262148 KB
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#include<bits/stdc++.h>
vector<pair<long long ,long long > >gr(300000 , {-1 , -1});
vector<vector<vector <pair<long long , long long> > > >lift(300000 , vector<vector<pair<long long , long long> > >(40 , { {-1 , -1} , {-1 , -1}} ));
vector<long long>pow2;
void count_routes(int menge, int ed, int gew, int edge[][2], int que, int  gru[]){
  for(long long i = 1; i <= 1000000000 ; i *= 2){
    pow2.push_back(i);
  }
  for(long long i = 0 ; i < ed; i++){
    if(gr[edge[i][0]].first == -1 ){
      gr[edge[i][0]].first = edge[i][1];
    }
    else if(gr[edge[i][0]].second == -1){
      gr[edge[i][0]].second = edge[i][1];
    }
    if(gr[edge[i][1]].first == -1){
      gr[edge[i][1]].first = edge[i][0];
    }
    else if(gr[edge[i][1]].second == -1){
      gr[edge[i][1]].second = edge[i][0];
    }
  }
  for(long long i = 0 ; i < menge ; i ++){
    // assert(gr[i].first != -1);
    if(gr[i].second == -1){
      gr[i].second = gr[i].first;
    }
    lift[i][0][0].first =gr[i].first;
    lift[i][0][0].second = i;

     
    lift[i][0][1].first =gr[i].second;
    lift[i][0][1].second = i;
    // cout << lift[i][0][0].first << ' ' << lift[i][0][1].first << "\n";
  }
  for(long long j = 1 ; j < 40 ; j++){
    for(long long i = 0 ; i < menge ; i++){
  // cout << "ja\n";
      long long fater = lift[i][j - 1][0].first;
      if(lift[i][j - 1][0].second == gr[fater].first){
        lift[i][j][0] = lift[fater][j - 1][1];
        // lift[i][j][0].second = lift[fater][j - 1][1].second;
      }
      else{
        lift[i][j][0] = lift[fater][j - 1][0];
      }


      fater = lift[i][j - 1][1].first;
      if(lift[i][j - 1][1].second == gr[fater].first){
        lift[i][j][1] = lift[fater][j - 1][1];
        // lift[i][j][0].second = lift[fater][j - 1][1].second;
      }
      else{
        lift[i][j][1] = lift[fater][j - 1][0];
      }
    }
  }
  while(true){
    
  }
  // for(long long i = 0 ; i < menge ; i++){
  //   for(long long j = 0 ; j  < 2 ; j++){
  //     cout << lift[i][j][0].first << ' ';
  //   }
  //   cout << "\n";
  // }
  long long rechner;
  for(long long i = 0 ; i < que ; i++){
    rechner = 0;
    // cout << gru[i] << "\n";
    for(long long j = 0 ; j < menge ; j++){
      // cout << "ja\n";
      long long jet = j , fl = 0 , cmp = gru[i];
      for(long long k = pow2.size() -1 ; k >= 0 ; k--){
        if(pow2[k] <= cmp){
          cmp -= pow2[k];
        // cout << "ja\n";
        // cout << jet << ' ' << k << ' ' << fl << ' ' << lift[jet][k][fl].first << "\n";
          if(lift[jet][k][fl].second == gr[lift[jet][k][fl].first].first){
          jet = lift[jet][k][fl].first;
            fl = 1;
          }
          else{
          jet = lift[jet][k][fl].first;
            fl = 0; 
          }
        }
      }

      // cout << "\n";
      if(jet == gew){
        rechner++;
      }
      // cout << jet << ' ';
    }
    answer(rechner);
    cout << "\n";
  }
}


# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -