///~~~LOTA~~~///
#include "garden.h"
#include "gardenlib.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);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
