Submission #1139456

#TimeUsernameProblemLanguageResultExecution timeMemory
1139456MamedovInside information (BOI21_servers)C++20
5 / 100
113 ms41520 KiB
#pragma GCC optimize ("O3") #include <bits/stdc++.h> #define vi vector<int> #define vll vector<ll> #define vvi vector<vi> #define oo 1000000001 #define eb emplace_back #define pb push_back #define mpr make_pair #define ln '\n' #define ull unsigned long long #define ll long long #define all(v) v.begin(), v.end() #define iospeed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> void show(vector<T> &v) { for (T i : v) { cout << i << ' '; } cout << ln; } struct CentroidDecomposition { vector<vector<array<int, 2>>>g; vector<bool>removed; vector<int>subSize; vector<vector<int>>cents; vector<vector<int>>incFromCent, incFromCentChild; vector<vector<array<int, 3>>>incToCentFrom; vector<vector<array<int, 2>>>decToCentFrom; int nxt = 0; CentroidDecomposition(int n, vector<array<int, 3>> &e) { g.resize(n + 1); for (auto [u, v, w] : e) { g[u].pb({v, w}); g[v].pb({u, w}); } removed.assign(n + 1, false); subSize.resize(n + 1); cents.resize(n + 1); incFromCent.resize(n + 1); incToCentFrom.resize(n + 1); decToCentFrom.resize(n + 1); } int getSubSize(int v, int pa = -1) { subSize[v] = 1; for (auto [to, w] : g[v]) { if (to != pa && !removed[to]) subSize[v] += getSubSize(to, v); } return subSize[v]; } int findCentroid(int v, int halfSize, int pa = -1) { for (auto [to, w] : g[v]) { if (to != pa && !removed[to] && subSize[to] > halfSize) return findCentroid(to, halfSize, v); } return v; } void getIncPaths(int v, int centroid, int centW, int pa, int prevW, bool isInc, bool isDec) { cents[v].pb(centroid); if (isInc) { //incFromCent[centroid].pb(prevW); incFromCentChild[nxt].pb(prevW); decToCentFrom[v].pb({centroid, prevW}); } if (isDec) { incToCentFrom[v].pb({centroid, nxt, centW}); } for (auto [to, w] : g[v]) { if (to != pa && !removed[to]) { if (isInc && w > prevW) getIncPaths(to, centroid, centW, v, w, true, false); else if (isDec && w < prevW) getIncPaths(to, centroid, centW, v, w, false, true); else getIncPaths(to, centroid, centW, v, w, false, false); } } } int build(int v = 1) { int centroid = findCentroid(v, getSubSize(v) >> 1); removed[centroid] = true; cents[centroid].pb(centroid); incToCentFrom[centroid].pb({centroid, -1, 0}); // for paths starting at centroid for (auto [to, w] : g[centroid]) { if (!removed[to]) { incFromCentChild.pb({}); getIncPaths(to, centroid, w, centroid, w, true, true); sort(all(incFromCentChild[nxt])); incFromCent[centroid].insert(incFromCent[centroid].end(), all(incFromCentChild[nxt])); nxt++; } } sort(all(incFromCent[centroid])); for (auto [to, w] : g[centroid]) { if (!removed[to]) build(to); } return centroid; } int count(int d, int id) { int res = 0; for (auto [centroid, centChild, w] : incToCentFrom[d]) { if (w < id) { res++; res += (upper_bound(all(incFromCent[centroid]), id) - upper_bound(all(incFromCent[centroid]), w)); if (centChild != -1) res -= (upper_bound(all(incFromCentChild[centChild]), id) - upper_bound(all(incFromCentChild[centChild]), w)); } } return res; } string ask(int a, int d, int id) { if (a == d) return "yes"; int cent = -1; int mn = min((int)cents[d].size(), (int)cents[a].size()); for (int i = 0; i < mn; ++i) { if (cents[d][i] == cents[a][i]) cent = cents[d][i]; else break; } int wd = oo; for (auto [centroid, centChild, w] : incToCentFrom[d]) { if (centroid == cent) { wd = w; break; } } if (cent == a && wd < id) return "yes"; int wa = oo; for (auto [centroid, w] : decToCentFrom[a]) { if (centroid == cent) { wa = w; break; } } if (wa > wd && wa < id) return "yes"; else return "no"; } }; void solve() { int n, k; cin >> n >> k; vector<array<int, 3>>e; vector<array<int, 3>>qrs; for (int i = 1; i < n + k; ++i) { char type; int u, v = -1; cin >> type >> u; if (type != 'C') cin >> v; if (type == 'S') { e.pb({u, v, i}); } else { qrs.pb({u, v, i}); } } CentroidDecomposition cd(n, e); cd.build(); for (auto [u, v, id] : qrs) { if (v == -1) { cout << cd.count(u, id) << ln; } else { cout << cd.ask(u, v, id) << ln; } } } int main() { iospeed; solve(); 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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...