Submission #685018

#TimeUsernameProblemLanguageResultExecution timeMemory
685018flappybirdSynchronization (JOI13_synchronization)C++17
0 / 100
8096 ms43244 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; #define MAX 202020 #define MAXS 20 #define INF 1000000000000000001 #define bb ' ' #define ln '\n' #define Ln '\n' pii edges[MAX]; vector<pii> toggle[MAX]; int laston[MAX]; vector<int> adj[MAX]; int ans[MAX]; int vis[MAX]; int num[MAX]; map<int, int> mp[MAX]; int findnxt(int v, int e) { return edges[e].first + edges[e].second - v; } map<int, int> mpall; int mpsum; void bottomup(int x, int p = 0, int isrt = 0) { mp[x].clear(); mp[x][0] = 1; int i; for (auto e : adj[x]) { int v = findnxt(x, e); if (vis[v] || v == p) continue; if (toggle[e].empty()) continue; bottomup(v, x); for (i = 0; i < toggle[e].size(); i++) { int s; if (i) s = toggle[e][i - 1].second; else s = -1; int nxt = toggle[e][i].first; while (1) { auto it = mp[v].lower_bound(s); if (it == mp[v].end()) break; if (it->first >= nxt) break; mp[v][nxt] += it->second; mp[v].erase(it); } } while (mp[v].size() && mp[v].rbegin()->first >= toggle[e].back().second) mp[v].erase(mp[v].rbegin()->first); if (!isrt) { if (mp[v].size() > mp[x].size()) swap(mp[v], mp[x]); for (auto& [a, b] : mp[v]) mp[x][a] += b; } } } void topdown(int x, int p) { ans[x] += mpsum; int i; for (auto e : adj[x]) { int v = findnxt(x, e); if (vis[v] || v == p) continue; if (toggle[e].empty()) continue; vector<pii> logv; for (i = 0; i < toggle[e].size(); i++) { int s; if (i) s = toggle[e][i - 1].second; else s = -1; int nxt = toggle[e][i].first; while (1) { auto it = mpall.lower_bound(s); if (it == mpall.end()) break; if (it->first >= nxt) break; logv.emplace_back(it->first, it->second); logv.emplace_back(nxt, -it->second); mpall[nxt] += it->second; mpall.erase(it); } } while (mpall.size() && mpall.rbegin()->first >= toggle[e].back().second) { mpsum -= mpall.rbegin()->second; logv.emplace_back(mpall.rbegin()->first, mpall.rbegin()->second); mpall.erase(mpall.rbegin()->first); } topdown(v, x); for (auto& [a, b] : logv) { mpall[a] += b, mpsum += b; if (!mpall[a]) mpall.erase(a); } } } void make_num(int x, int p = 0) { mp[x].clear(); num[x] = 1; for (auto e : adj[x]) { int v = findnxt(x, e); if (v == p || vis[v]) continue; make_num(v, x); num[x] += num[v]; } } void make_tree(int x) { make_num(x); int c = x; int n = num[x]; while (1) { int changed = 0; for (auto e : adj[c]) { int v = findnxt(c, e); if (!vis[v] && num[v] < num[c]) { if (num[v] > n / 2) { c = v; changed = 1; break; } } } if (!changed) break; } bottomup(c, 0, 1); mpall.clear(); mpsum = 0; for (auto e : adj[c]) { int v = findnxt(c, e); if (vis[v]) continue; if (mpall.size() < mp[v].size()) swap(mpall, mp[v]); for (auto& [a, b] : mp[v]) if (b) mpall[a] += b, mpsum += b; } for (auto& [a, b] : mp[c]) if (b) mpall[a] += b, mpsum += b; ans[c] += mpsum; int i; for (auto e : adj[c]) { int v = findnxt(c, e); if (vis[v]) continue; if (toggle[e].empty()) continue; for (auto& [a, b] : mp[v]) if (b) mpall[a] -= b, mpsum -= b; vector<pii> logv; for (i = 0; i < toggle[e].size(); i++) { int s; if (i) s = toggle[e][i - 1].second; else s = -1; int nxt = toggle[e][i].first; while (1) { auto it = mpall.lower_bound(s); if (it == mpall.end()) break; if (it->first >= nxt) break; logv.emplace_back(it->first, it->second); logv.emplace_back(nxt, -it->second); mpall[nxt] += it->second; mpall.erase(it); } } while (mpall.size() && mpall.rbegin()->first >= toggle[e].back().second) { mpsum -= mpall.rbegin()->second; logv.emplace_back(mpall.rbegin()->first, mpall.rbegin()->second); mpall.erase(mpall.rbegin()->first); } topdown(v, c); for (auto& [a, b] : logv) { mpall[a] += b, mpsum += b; if (!mpall[a]) mpall.erase(a); } for (auto& [a, b] : mp[v]) if (b) { mpall[a] += b, mpsum += b; if (!mpall[a]) mpall.erase(a); } } vis[c] = 1; for (auto e : adj[c]) { int v = findnxt(c, e); if (!vis[v]) make_tree(v); } } signed main() { ios::sync_with_stdio(false), cin.tie(0); int N, M, Q; cin >> N >> M >> Q; int i, a, b; for (i = 1; i < N; i++) { cin >> a >> b; edges[i] = pii(a, b); adj[a].push_back(i); adj[b].push_back(i); } for (i = 1; i <= M; i++) { cin >> a; if (laston[a]) { toggle[a].emplace_back(laston[a], i); laston[a] = 0; } else laston[a] = i; } for (i = 1; i < N; i++) if (laston[i]) toggle[i].emplace_back(laston[i], M + 1); make_tree(1); vector<int> qs; while (Q--) { cin >> a; qs.push_back(a); } for (auto v : qs) cout << ans[v] << ln; }

Compilation message (stderr)

synchronization.cpp: In function 'void bottomup(int, int, int)':
synchronization.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for (i = 0; i < toggle[e].size(); i++) {
      |               ~~^~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'void topdown(int, int)':
synchronization.cpp:64:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (i = 0; i < toggle[e].size(); i++) {
      |               ~~^~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'void make_tree(int)':
synchronization.cpp:137:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for (i = 0; i < toggle[e].size(); i++) {
      |               ~~^~~~~~~~~~~~~~~~~~
#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...