Submission #399012

#TimeUsernameProblemLanguageResultExecution timeMemory
399012Pichon5Tropical Garden (IOI11_garden)C++17
0 / 100
3 ms4300 KiB
#include <bits/stdc++.h> #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=150000; const int MA=29; int up[tam][MA]; int up2[tam][MA]; int last[tam][MA]; int last2[tam][MA]; 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()<2)G[i].pb(G[i][0]); up[i][0]=G[i][0].F; last[i][0]=G[i][0].S; up2[i][0]=G[i][1].F; last2[i][0]=G[i][1].S; } for(int i=1;i<=MA;i++){ for(int nodo=0;nodo<n;nodo++){ if(G[nodo].size()==0)continue; int mid=up[nodo][i-1]; up[nodo][i]=up[mid][i-1]; last[nodo][i]=last[mid][i-1]; if(last[mid][0]==last[nodo][i-1]){ up[nodo][i]=up2[mid][i-1]; last[nodo][i]=last2[mid][i-1]; } mid=up2[nodo][i-1]; up2[nodo][i]=up[mid][i-1]; last2[nodo][i]=last[mid][i-1]; if(last2[nodo][i-1]==last[mid][0]){ up2[nodo][i]=up2[mid][i-1]; last2[nodo][i]=last2[mid][i-1]; } } } int k=g[0]; int res=0; for(int i=0;i<n;i++){ int nodo=i; int ant=-1; for(int l=MA;l>=0;l--){ if((1<<l)&k){ if(ant!=last[nodo][0]){ ant=last[nodo][l]; nodo=up[nodo][l]; }else{ ant=last2[nodo][l]; nodo=up2[nodo][l]; } } } 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...