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...