이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 500005;
vector<pair<int,int>> adj[MAXN];
int nxt[MAXN][30];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
for(int i=0;i<M;i++){
adj[R[i][0]].push_back({i,R[i][1]});
adj[R[i][1]].push_back({i,R[i][0]});
}
for(int i=0;i<N;i++){
sort(adj[i].begin(),adj[i].end());
}
for(int i=0;i<N;i++){
int here = i;
int there = adj[i][0].second;
nxt[i][0] = adj[i][0].second;
if(adj[there][0].second == here) nxt[here][0] += N;
there = nxt[i+N][0] = (adj[i].size() == 1) ? adj[i][0].second : adj[i][1].second;
here = i + N;
if(adj[there][0].second == here-N) nxt[here][0] += N;
}
for(int i=1;i<30;i++){
for(int j=0;j<2*N;j++){
nxt[j][i] = nxt[nxt[j][i-1]][i-1];
}
}
for(int k=0;k<Q;k++){ // 반
int cnt = 0;
for(int i=0;i<N;i++){ //시작점
int bit = G[k];
int j = 0;
int cur = i;
while(bit){
if(bit & (1<<j)){
bit -= (1<<j);
cur = nxt[cur][j];
}
j++;
}
if(cur == P || cur -N == P) cnt++;
}
answer(cnt);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |