| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 39548 | 2018-01-16T12:32:36 Z | smu201111192 | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++14 | 0 ms | 0 KB |
#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[])
{
::N= N;
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);
}
}