oj.uz

Submission #534976

# Submission time Handle Problem Language Result Execution time Memory
534976 2022-03-09T08:16:39 Z almothana05 Tropical Garden (IOI11_garden) C++14
49 / 100
 11 ms 7532 KB 
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#include<bits/stdc++.h>
vector<pair<int ,int > >gr(1500 , {-1 , -1});
vector<vector<vector <pair<int , int> > > >lift(1500 , vector<vector<pair<int , int> > >(40 , { {-1 , -1} , {-1 , -1}} ));
vector<int>pow2;
void count_routes(int menge, int ed, int gew, int edge[][2], int que, int  gru[]){
  // while(true){}
  for(int i = 1; i <= 1000000000 ; i *= 2){
    pow2.push_back(i);
  }
  for(int 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(int 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(int j = 1 ; j < 40 ; j++){
    for(int i = 0 ; i < menge ; i++){
  // cout << "ja\n";
      int 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];
      }
    }
  }
  // for(int i = 0 ; i < menge ; i++){
  //   for(int j = 0 ; j  < 2 ; j++){
  //     cout << lift[i][j][0].first << ' ';
  //   }
  //   cout << "\n";
  // }
  int rechner;
  for(int i = 0 ; i < que ; i++){
    rechner = 0;
    // cout << gru[i] << "\n";
    for(int j = 0 ; j < menge ; j++){
      // cout << "ja\n";
      int jet = j , fl = 0 , cmp = gru[i];
      for(int 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";
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3660 KB Output is correct
2 Correct 4 ms 3660 KB Output is correct
3 Correct 5 ms 3660 KB Output is correct
4 Correct 4 ms 3660 KB Output is correct
5 Correct 4 ms 3660 KB Output is correct
6 Correct 5 ms 3660 KB Output is correct
7 Correct 4 ms 3660 KB Output is correct
8 Correct 4 ms 3660 KB Output is correct
9 Correct 7 ms 3736 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3660 KB Output is correct
2 Correct 4 ms 3660 KB Output is correct
3 Correct 5 ms 3660 KB Output is correct
4 Correct 4 ms 3660 KB Output is correct
5 Correct 4 ms 3660 KB Output is correct
6 Correct 5 ms 3660 KB Output is correct
7 Correct 4 ms 3660 KB Output is correct
8 Correct 4 ms 3660 KB Output is correct
9 Correct 7 ms 3736 KB Output is correct
10 Correct 4 ms 3660 KB Output is correct
11 Runtime error 11 ms 7532 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3660 KB Output is correct
2 Correct 4 ms 3660 KB Output is correct
3 Correct 5 ms 3660 KB Output is correct
4 Correct 4 ms 3660 KB Output is correct
5 Correct 4 ms 3660 KB Output is correct
6 Correct 5 ms 3660 KB Output is correct
7 Correct 4 ms 3660 KB Output is correct
8 Correct 4 ms 3660 KB Output is correct
9 Correct 7 ms 3736 KB Output is correct
10 Correct 4 ms 3660 KB Output is correct
11 Runtime error 11 ms 7532 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -