#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][31][2];
// map<int , <vector<vector <pair<int , int> > > >lift(150000 , vector<vector<pair<int , int> > >(31 , { {-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";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
