| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 347834 | tengiz05 | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}