Submission #1300537

#TimeUsernameProblemLanguageResultExecution timeMemory
1300537Hamed_GhaffariSynchronization (JOI13_synchronization)C++20
40 / 100
8092 ms17964 KiB
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pli pair<ll, ll>
#define ppi pair<pii, pii>
#define RUN_LIKE_DJAWAD (ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0));
#define DECIMAL_OUTPUT cout << fixed << setprecision(9);
#define pb push_back
#define pf push_top
#define ff first
#define ss second
#define maxn 200001
#define sq 1200
 
bool ac[maxn], seen[maxn], fac[maxn];
int gr[maxn], cnt[maxn], ans[maxn], ag[maxn];
 
vector<int> go[maxn], gv[maxn];
 
pii e[maxn];
 
int n, m, q, pt, ei, gpt;
 
vector<int> now;
 
vector<int> adj[maxn];
 
void dfs(int v){
 
    seen[v] = true;
    gv[gpt].pb(v);
    gr[v] = gpt;
    ag[gpt] = ans[v];
 
    for (int u: adj[v]) if (not seen[u]) dfs(u);
}
 
vector<pii> g[maxn];
 
int vs;
 
void mdfs(int v){
 
    seen[v] = true;
    ag[v] = vs;
 
    for (auto [u, ind]: g[v]) if (not seen[u] and ac[ind]) mdfs(u);
 
    seen[v] = false;
 
}
 
void JL(){
 
    if (now.empty()) return;
 
    for (int i = 1; i < n; i++) fac[i] = ac[i];
    for (int i: now) fac[i] = false;
 
    for (int i = 1; i < n; i++) if (fac[i]){
 
        adj[e[i].ff].pb(e[i].ss);
        adj[e[i].ss].pb(e[i].ff);
    }
 
    gpt = 0;
 
    for (int i: now){
 
        if (not seen[e[i].ff]){
 
            dfs(e[i].ff);
            gpt++;
        }
 
        if (not seen[e[i].ss]){
 
            dfs(e[i].ss);
            gpt++;
        }
    }
 
    for (int i = 1; i <= n; i++) seen[i] = false;
 
    for (int i: now){
 
        g[gr[e[i].ff]].pb({gr[e[i].ss], i});
        g[gr[e[i].ss]].pb({gr[e[i].ff], i});
    }
 
    for (int i: now){
 
        if (ac[i]){
 
            cnt[i] = ag[gr[e[i].ff]];
            ac[i] = false;
 
        } else {
 
            ac[i] = true;
 
            vs = ag[gr[e[i].ff]] + ag[gr[e[i].ss]] - cnt[i];
            mdfs(gr[e[i].ff]);
        }
    }
 
    for (int i = 0; i < gpt; i++) for (int u: gv[i]) ans[u] = ag[i];
 
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (int i = 0; i < gpt; i++) g[i].clear(), gv[i].clear();
}
 
int qi;
 
int main(){
 
    RUN_LIKE_DJAWAD
 
    cin >> n >> m >> q;
 
    for (int i = 1; i <= n; i++) ans[i] = 1;
 
    for (int i = 1; i < n; i++) cin >> e[i].ff >> e[i].ss;
 
    for (int i = 1; i <= m; i++){
 
        cin >> ei;
 
        go[pt].pb(ei);
 
        if (i % sq == 0) pt++;
    }
 
    for (int i = 0; i < maxn; i++){
 
        now = go[i];
 
        JL();
    }
 
    while (q--){
 
        cin >> qi;
 
        cout << ans[qi] << "\n";
    }
}
#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...