| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1105180 | 2024-10-25T16:10:16 Z | anarch_y | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++17 | 0 ms | 0 KB |
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
int main(){
int n, m; cin >> n >> m;
vector<pair<int, int>> vec[n];
int mn[n] = {};
for(int i=1; i<=m; i++){
int a, b; cin >> a >> b;
vec[a].pb({b, i}); vec[b].pb({a, i});
if(mn[a] == 0) mn[a] = i;
if(mn[b] == 0) mn[b] = i;
}
int to[2*n] = {};
for(int a=0; a<n; a++){
auto [b, i] = vec[a][0];
if(mn[b] == i) to[a] = n+b;
else to[a] = b;
if(sz(vec[a]) >= 2){
auto [c, j] = vec[a][1];
if(mn[c] == j) to[n+a] = n+c;
else to[n+a] = c;
}
else{
if(mn[b] == i) to[n+a] = n+b;
else to[n+a] = b;
}
}
int succ[2*n][20] = {};
for(int a=0; a<2*n; a++){
succ[a][0] = to[a];
}
for(int i=1; i<20; i++){
for(int a=0; a<2*n; a++){
succ[a][i] = succ[succ[a][i-1]][i-1];
}
}
int p; cin >> p;
int q; cin >> q;
int qry[q] = {};
for(int i=0; i<q; i++) cin >> qry[i];
for(int i=0; i<q; i++){
int k = qry[i];
int ans = 0;
for(int a=0; a<n; a++){
int x = a;
for(int i=0; i<20; i++){
if(k & (1<<i)) x = succ[x][i];
}
if(x == p or x == n+p) ans++;
}
answer(ans);
}
}