oj.uz

Submission #534991

# Submission time Handle Problem Language Result Execution time Memory
534991 2022-03-09T08:36:22 Z almothana05 Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 96644 KB 
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#include<bits/stdc++.h>
vector<pair<int ,int > >gr(150000 , {-1 , -1});
pair<int , int>lift[150000][40][2];
// vector<vector<vector <pair<int , int> > > >lift(150000 , 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 = 0 ; i < 150000 ; i++){
    for(int j = 0 ; j < 40 ; j++){
      lift[i][j][0] = {-1 , -1};
      lift[i][j][0] = {-1 , -1};
    }
  }
  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 41 ms 95300 KB Output is correct
2 Correct 43 ms 95392 KB Output is correct
3 Correct 51 ms 95332 KB Output is correct
4 Correct 44 ms 95296 KB Output is correct
5 Correct 39 ms 95348 KB Output is correct
6 Correct 41 ms 95364 KB Output is correct
7 Correct 42 ms 95512 KB Output is correct
8 Correct 45 ms 95396 KB Output is correct
9 Correct 46 ms 95468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 95300 KB Output is correct
2 Correct 43 ms 95392 KB Output is correct
3 Correct 51 ms 95332 KB Output is correct
4 Correct 44 ms 95296 KB Output is correct
5 Correct 39 ms 95348 KB Output is correct
6 Correct 41 ms 95364 KB Output is correct
7 Correct 42 ms 95512 KB Output is correct
8 Correct 45 ms 95396 KB Output is correct
9 Correct 46 ms 95468 KB Output is correct
10 Correct 50 ms 95392 KB Output is correct
11 Correct 57 ms 95468 KB Output is correct
12 Correct 78 ms 95760 KB Output is correct
13 Correct 213 ms 96164 KB Output is correct
14 Correct 201 ms 96468 KB Output is correct
15 Correct 189 ms 96588 KB Output is correct
16 Correct 155 ms 96556 KB Output is correct
17 Correct 179 ms 96452 KB Output is correct
18 Correct 74 ms 95892 KB Output is correct
19 Correct 195 ms 96552 KB Output is correct
20 Correct 197 ms 96644 KB Output is correct
21 Correct 151 ms 96452 KB Output is correct
22 Correct 148 ms 96552 KB Output is correct
23 Correct 226 ms 96592 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 95300 KB Output is correct
2 Correct 43 ms 95392 KB Output is correct
3 Correct 51 ms 95332 KB Output is correct
4 Correct 44 ms 95296 KB Output is correct
5 Correct 39 ms 95348 KB Output is correct
6 Correct 41 ms 95364 KB Output is correct
7 Correct 42 ms 95512 KB Output is correct
8 Correct 45 ms 95396 KB Output is correct
9 Correct 46 ms 95468 KB Output is correct
10 Correct 50 ms 95392 KB Output is correct
11 Correct 57 ms 95468 KB Output is correct
12 Correct 78 ms 95760 KB Output is correct
13 Correct 213 ms 96164 KB Output is correct
14 Correct 201 ms 96468 KB Output is correct
15 Correct 189 ms 96588 KB Output is correct
16 Correct 155 ms 96556 KB Output is correct
17 Correct 179 ms 96452 KB Output is correct
18 Correct 74 ms 95892 KB Output is correct
19 Correct 195 ms 96552 KB Output is correct
20 Correct 197 ms 96644 KB Output is correct
21 Correct 151 ms 96452 KB Output is correct
22 Correct 148 ms 96552 KB Output is correct
23 Correct 226 ms 96592 KB Output is correct
24 Correct 56 ms 95340 KB Output is correct
25 Execution timed out 5012 ms 95672 KB Time limit exceeded
26 Halted 0 ms 0 KB -