JAPLJ Contest B: Banksia
問題
http://judge.imoz.jp/page.php?page=view_problem&pid=43&cid=8
回答(1回目) - Accepted
#include <cstdio> #include <vector> using namespace std; int A[100100]; int B[100100]; int C[100100]; int main() { int N, K; scanf("%d %d", &N, &K); int NN = N; for (int k = 0; ; ++ k) { for (int i = 0; i < N; ++ i) { int n; scanf("%d", &n); A[i] = n; if (k > 0 && B[ A[i] ] >= 0) { C[ B[ A[i] ] ] = A[i]; } } for (int i = 1; i <= N; ++ i) { B[i] = -1; } for (int i = 0; i < N/2; ++ i) { B[ A[2*i] ] = A[2*i+1]; B[ A[2*i+1] ] = A[2*i]; } if (N == 1) break; N = (N-1)/2 + 1; } for (int i = 1; i <= NN; ++ i) { int k = 0; for (int p = i; C[p]; p = C[p]) { ++ k; } if (k < K) { printf("%d\n", i); } } }