# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
898709 | 2024-01-05T03:51:18 Z | Sir_Ahmed_Imran | Tropical Garden (IOI11_garden) | C++17 | 0 ms | 0 KB |
///~~~LOTA~~~/// #include "garden.h" #include <bits/stdc++.h> using namespace std; #define nl '\n' #define ff first #define ss second #define ll long long #define append push_back #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define MAXN 150000 int pwr[30]; int lv[MAXN][2]; vector<pii> a[MAXN]; int pre[MAXN][30][2]; int nxt[MAXN][30][2]; map<int,int> is[MAXN]; void count_routes(int n,int m,int x,int e[MAXN][2],int Q,int G[MAXN]){ int o,p,q,r,s; for(int i=0;i<m;i++){ a[e[i][0]].append({e[i][1],i}); a[e[i][1]].append({e[i][0],i}); } for(int i=pwr[0]=1;i<30;i++) pwr[i]=pwr[i-1]*2; for(int i=0;i<n;i++){ p=q=m; for(auto& j:a[i]){ if(j.ss<p){ q=p; p=j.ss; lv[i][1]=lv[i][0]; lv[i][0]=j.ff; } else if(j.ss<q){ q=j.ss; lv[i][1]=j.ff; } } pre[i][0][0]=pre[i][0][1]=i; if(q==m) lv[i][1]=lv[i][0]; nxt[i][0][0]=lv[i][0]; nxt[i][0][1]=lv[i][1]; is[i][lv[i][0]]=1; } for(int j=0;j<29;j++){ for(int i=0;i<n;i++){ nxt[i][j+1][0]=nxt[nxt[i][j][0]][j][is[nxt[i][j][0]][pre[i][j][0]]]; pre[i][j+1][0]=pre[nxt[i][j][0]][j][is[nxt[i][j][0]][pre[i][j][0]]]; nxt[i][j+1][1]=nxt[nxt[i][j][1]][j][is[nxt[i][j][1]][pre[i][j][0]]]; pre[i][j+1][1]=pre[nxt[i][j][1]][j][is[nxt[i][j][1]][pre[i][j][0]]]; } } for(int k=0;k<Q;k++){ for(int i=o=0;i<n;i++){ p=-1; q=i; r=G[k]; for(int j=29;j>=0;j--){ if(pwr[j]>i) continue; r-=j; s=is[q][p]; p=pre[q][j][s]; q=nxt[q][j][s]; } o+=(q==x); } answer(o); } }