| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 347834 | tengiz05 | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "garden.h"
#include "gardenlib.h"
//~ #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
const int N_ = 150005;
int ans, n, m, target;
vector<int> edges[N_];
int d;
int nxt[N_*2][30];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
target = P;
n = N, m = M;
for(int i=0;i<m;i++){
if(edges[R[i][0]].size() < 2)edges[R[i][0]].pb(R[i][1]);
if(edges[R[i][1]].size() < 2)edges[R[i][1]].pb(R[i][0]);
}
for(int i=0;i<n;i++){
nxt[i][0] = i;
}
for(int i=0;i<n;i++){
for(int j=0;j<(int)edges[i].size();j++){
int to = edges[i][j];
if(edges[to][j] == i && edges[to].size() == 2){
nxt[i+j*n][0] = to+n;
}else {
nxt[i+j*n][0] = to;
}
}
}
for(int i=1;i<30;i++){
for(int u=0;u<n*2;u++){
nxt[u][i] = nxt[nxt[u][i-1]][i-1];
}
}
for(int q=0;q<Q;q++){
int t = G[q];
int ans = 0;
for(int i=0;i<n;i++){
int s = i;
for(int j=0;j<29;j++){
if((1<<j)&t)s = nxt[s][j];
}ans += (s == P || s-n == P);
}answer(ans);
}return;
}