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