| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1237887 | nastya_an | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define cin(v) \
for (auto &el : v) { cin >> el; }
#define cout(v) \
for (auto &el : v) { cout << el << " "; } \
cout << "\n";
using namespace std;
using ll = long long;
using db = double;
using ldb = long double;
const ldb EPS = 1e-9;
const ll LINF = 2e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 1072005019;
const ll MOD3 = 998244353;
const ldb PI = acos(-1.0);
vector<vector<int>> g;
vector<int> nxt, used, len_cycle, cycle_num_vert, first_vert, len_to_cycle, type_cycle, in_cycle_;
bool in_cycle = 0;
int first_vert_cur_cycle = -1, len = 0, type = 0;
vector<int> cycle;
void dfs(int v) {
if (used[v] == 2) {
return;
}
if (used[v] == 1) {
in_cycle = 1;
first_vert_cur_cycle = v;
return;
}
used[v] = 1;
dfs(nxt[v]);
if (in_cycle) {
in_cycle_[v] = 1;
len++;
cycle.push_back(v);
first_vert[v] = v;
type_cycle[v] = type;
} else {
len_to_cycle[v] = len_to_cycle[nxt[v]] + 1;
first_vert[v] = first_vert[nxt[v]];
type_cycle[v] = type_cycle[nxt[v]];
len_cycle[v] = len;
}
if (v == first_vert_cur_cycle) {
in_cycle = 0;
first_vert_cur_cycle= -1;
}
used[v] = 2;
}
void solve() {
int n, m, p;
cin >> n >> m >> p;
g.resize(n);
for (int i = 0; i < m; i++) {
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
nxt.resize(2 * n);
used.resize(2 * n);
len_cycle.resize(2 * n);
cycle_num_vert.resize(2 * n);
type_cycle.resize(2 * n);
first_vert.resize(2 * n);
len_to_cycle.resize(2 * n);
in_cycle_.resize(2 * n);
for (int v = 0; v < n; v++) {
int to = g[v][0];
if (g[to][0] == v && g[to].size() >= 2) {
nxt[v] = to + n;
} else {
nxt[v] = to;
}
if (g[v].size() >= 2) {
int to2 = g[v][1];
if (g[to2][0] == v && g[to2].size() >= 2) {
nxt[v + n] = to2 + n;
} else {
nxt[v + n] = to2;
}
} else {
nxt[v + n] = nxt[v];
}
}
g.resize(0);
g.resize(2 * n);
for (int v = 0; v < 2 * n; v++) {
g[nxt[v]].push_back(v);
}
for (int v = 0; v < 2 * n; v++) {
type = v;
dfs(v);
int i = 0;
if (cycle.size()) {
for (int v : cycle) {
cycle_num_vert[v] = i;
len_cycle[v] = len;
i++;
}
cycle.resize(0);
}
}
vector<int> len1(2 * n), len2(2 * n);
vector<int> stack = {p};
while (stack.size()) {
int v = stack.back();
stack.pop_back();
for (int to : g[v]) {
if (len1[to] > 0 || to == p) {
continue;
}
len1[to] = len1[v] + 1;
stack.push_back(to);
}
}
stack.clear();
stack.push_back(p + n);
while (stack.size()) {
int v = stack.back();
stack.pop_back();
for (int to : g[v]) {
if (len2[to] > 0 || to == p + n) {
continue;
}
len2[to] = len2[v] + 1;
stack.push_back(to);
}
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int k;
cin >> k;
int ans = 0;
//p
if (in_cycle_[p]) {
for (int v = 0; v < n; v++) {
if (type_cycle[v] != type_cycle[p]) {
continue;
}
int v_ = first_vert[v];
int len_ = len_to_cycle[v];
if (cycle_num_vert[v_] >= cycle_num_vert[p]) {
len_ += cycle_num_vert[v_] - cycle_num_vert[p];
} else {
len_ += len_cycle[v_] - (cycle_num_vert[p] - cycle_num_vert[v_]);
}
if (len_ <= k && k % len_cycle[v_] == len_ % len_cycle[v_]) {
ans++;
}
}
} else {
for (int v = 0; v < n; v++) {
if (len1[v] >= k) {
ans++;
}
}
}
//p + n
if (in_cycle_[p + n]) {
for (int v = 0; v < n; v++) {
if (type_cycle[v] != type_cycle[p + n]) {
continue;
}
int v_ = first_vert[v];
int len_ = len_to_cycle[v];
if (cycle_num_vert[v_] >= cycle_num_vert[p + n]) {
len_ += cycle_num_vert[v_] - cycle_num_vert[p + n];
} else {
len_ += len_cycle[v_] - (cycle_num_vert[p + n] - cycle_num_vert[v_]);
}
if (len_ <= k && k % len_cycle[v_] == len_ % len_cycle[v_]) {
ans++;
}
}
} else {
for (int v = 0; v < n; v++) {
if (len2[v] >= k) {
ans++;
}
}
}
cout << ans << " ";
}
return;
}
signed main() {
ll interactive = 0;
ll multitest = 0;
if (!interactive) {
ios_base::sync_with_stdio(0);
cin.tie(0);
}
if (multitest) {
ll T;
cin >> T;
while (T--) {
solve();
}
} else {
solve();
}
return 0;
}