제출 #1338933

#제출 시각아이디문제언어결과실행 시간메모리
1338933f0rizenSynchronization (JOI13_synchronization)C++20
40 / 100
8090 ms16004 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

vector<vector<pair<int, int>>> g;
vector<vector<pair<int, int>>> seg;
int r = inf;
int cnt = 0;

void dfs(int v, int p = -1) {
    ++cnt;
    for (auto [u, i] : g[v]) {
        if (u != p) {
            auto it = lower_bound(seg[i].begin(), seg[i].end(), pair{r, inf});
            if (it != seg[i].begin()) {
                int was = r;
                r = min(r, prev(it)->second);
                dfs(u, v);
                r = was;
            }
        }
    }
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, m, q;
    cin >> n >> m >> q;
    g.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    seg.resize(n - 1);
    for (int i = 0; i < m; ++i) {
        int e;
        cin >> e;
        --e;
        if (seg[e].empty() || seg[e].back().second != m - 1) {
            seg[e].push_back({i, m - 1});
        } else {
            seg[e].back().second = i - 1;
        }
    }
    while (q--) {
        int v;
        cin >> v;
        --v;
        r = inf;
        cnt = 0;
        dfs(v);
        cout << cnt << "\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...