제출 #398998

#제출 시각아이디문제언어결과실행 시간메모리
398998Pichon5열대 식물원 (Tropical Garden) (IOI11_garden)C++17
0 / 100
13 ms24100 KiB
#include<bits/stdc++.h> #include <iostream> #include "garden.h" #include "gardenlib.h" #define lcm(a,b) (a/__gcd(a,b))*b #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ll long long int #define vi vector<int> #define vll vector<ll> #define pb push_back #define F first #define S second #define mp make_pair using namespace std; const int tam=1e6; int up[tam][21]; int up2[tam][21]; int last[tam][21]; int last2[tam][21]; vector<pair<int,int> > G[tam]; void count_routes(int N, int M, int P, int R[][2], int Q, int g[]) { int n=N; for(int i=0;i<M;i++){ int a=R[i][0],b=R[i][1]; if(G[a].size()<2)G[a].pb({b,i}); if(G[b].size()<2)G[b].pb({a,i}); } for(int i=0;i<n;i++){ if(G[i].size()==0)continue; up[i][0]=up2[i][0]=G[i][0].F; last[i][0]=last2[i][0]=G[i][0].S; if(G[i].size()==2){ up2[i][0]=G[i][1].F; last2[i][0]=G[i][1].S; } } //for(int i=0;i<n;i++){ // cout<<i<<" -> "<<up2[i][0]<<endl; //} for(int i=1;i<=20;i++){ //cout<<"i "<<i<<endl bool ok=0; for(int nodo=0;nodo<n;nodo++){ if(!ok){ //cout<<"etro "<<i<<endl; ok=1; } if(G[nodo].size()==0)continue; int mid=up[nodo][i-1]; //cout<<mid<<endl; if(up[mid][0]!=last[nodo][i-1]){ up[nodo][i]=up[mid][i-1]; last[nodo][i]=last[mid][i-1]; }else{ if(nodo==0 && i==2){ //cout<<"aux "<<up2[mid][0]<<" "<<up2[mid][1]<<endl; //cout<<"mid "<<mid<<" "<<up2[mid][i-1]<<endl; } up[nodo][i]=up2[mid][i-1]; last[nodo][i]=last2[mid][i-1]; } //cout<<last[3][1]<<endl; //------------------ mid=up2[nodo][i-1]; if(last2[nodo][i-1]!=up[mid][0]){ if(nodo==2 && i==1){ //cout<<"mid "<<mid<<endl; //cout<<last2[nodo][i-1]<<" = "<<up[mid][0]<<endl; //cout<<"aqui se jodeeeee"<<endl; } up2[nodo][i]=up[mid][i-1]; last2[nodo][i]=last[mid][i-1]; }else{ up2[nodo][i]=up2[mid][i-1]; last2[nodo][i]=last2[mid][i-1]; } } } /*cout<<up[2][1]<<endl; for(int i=0;i<19;i++){ cout<<i<<" -> "<<up[0][i]<<" "<<last[0][i]<<endl; } cout<<endl; */ int k=g[0]; int res=0; /*for(int i=0;i<n;i++){ cout<<"para "<<i<<endl; for(int l=0;l<5;l++){ cout<<up[i][l]<<" "; } cout<<endl; }*/ for(int i=0;i<n;i++){ int nodo=i; int ant=-1; if(G[nodo].size()==0){ if(nodo==P)res++; continue; } //cout<<"empiezo en "<<i<<endl; for(int l=20;l>=0;l--){ if((1<<l)&k){ if(ant!=up[nodo][0]){ ant=last[nodo][l]; nodo=up[nodo][l]; }else{ ant=last2[nodo][l]; nodo=up2[nodo][l]; } //cout<<"subo "<<(1<<l)<<" "<<nodo<<" "<<ant<<endl; } } if(nodo==P)res++; } answer(res); } /* 5 5 2 1 0 1 2 3 2 1 3 4 2 1 3 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...