| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 534962 | 2022-03-09T07:58:23 Z | almothana05 | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++14 | 0 ms | 0 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 long longu[]){
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];
}
}
}
// 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";
}
}