Submission #57611

#TimeUsernameProblemLanguageResultExecution timeMemory
57611model_codeCollapse (JOI18_collapse)C++17
100 / 100
7553 ms30812 KiB
#include "collapse.h" #include <utility> #include <algorithm> #include <set> #include <iostream> #include <memory> template<typename T> using vector = std::vector<T>; template<typename T> using set = std::set<T>; template<typename T, typename S> using pair = std::pair<T, S>; using std::make_pair; using Paths = vector<pair<int, int>>; const int Bucket = 1000; class UnionFind { private: vector<int> parent; vector<int> rank; bool need_change; vector<int> change; public: UnionFind(int n, bool need_change_ = false) : parent(n), rank(n, 0), need_change(need_change_) { for(int i = 0; i < n; i++) parent[i] = i; } int findParent(int x) { if(parent[x] == x) return x; return parent[x] = findParent(parent[x]); } bool unionGroup(int x, int y) { int xp = findParent(x); int yp = findParent(y); if(xp == yp) { return false; } else { if(need_change) { change.push_back(xp); change.push_back(yp); } if(rank[xp] > rank[yp]) { parent[yp] = xp; } else if(rank[xp] < rank[yp]) { parent[xp] = yp; } else { parent[yp] = xp; rank[xp]++; } return true; } } void reset() { for(auto i : change) { parent[i] = i; rank[i] = 0; } change.clear(); } }; vector<pair<int, int>> solve( int n, Paths fixed, vector<pair<int, pair<int, std::shared_ptr<Paths>>>> query ) { auto comp_second = [](const pair<int, int>& a, const pair<int, int>& b){ return a.second < b.second; }; auto comp_first_only = [](const pair<int, pair<int, std::shared_ptr<Paths>>>& a, const pair<int, pair<int, std::shared_ptr<Paths>>>& b){ return a.first < b.first; }; sort(fixed.begin(), fixed.end(), comp_second); sort(query.begin(), query.end(), comp_first_only); vector<pair<int, int>> ret; UnionFind large(n), tmp(n, true); int now = 0; int count = 0; for(auto i : query) { while(now < (int)fixed.size() && fixed[now].second <= i.first) { if(large.unionGroup(fixed[now].first, fixed[now].second)) count++; now++; } int c = count; for(auto j : *i.second.second) if(j.second <= i.first && tmp.unionGroup(large.findParent(j.first), large.findParent(j.second))) c++; ret.push_back(make_pair(i.second.first, i.first + 1 - c)); tmp.reset(); } return ret; } pair<int, int> minMaxPair(int a, int b) { return make_pair(std::min(a, b), std::max(a, b)); } pair<int, int> revPath(int n, pair<int, int> p) { return make_pair(n - 1 - p.second, n - 1 - p.first); } vector<int> simulateCollapse( int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P ) { vector<pair<pair<int, int>, int>> q; for(int i = 0; i < (int)W.size(); i++) { q.push_back(make_pair(make_pair(W[i], P[i]), i)); } sort(q.begin(), q.end()); vector<int> ans(q.size(), 0); set<pair<int, int>> path; int now = 0; for(int s = 0; s < (int)T.size(); s += Bucket) { int e = std::min(s + Bucket, (int)T.size()); set<pair<int, int>> change; for(int i = s; i < e; i++) change.insert(minMaxPair(X[i], Y[i])); auto fixed_ = path; set<pair<int, int>> np; for(auto i : change) if(fixed_.find(i) != fixed_.end()) { fixed_.erase(i); np.insert(i); } Paths fixed1, fixed2; for(auto i : fixed_) { fixed1.push_back(i); fixed2.push_back(revPath(N, i)); } vector<pair<int, pair<int, std::shared_ptr<Paths>>>> query1, query2; for(int i = s; i < e; i++) { if(T[i] == 0) { path.insert(minMaxPair(X[i], Y[i])); np.insert(minMaxPair(X[i], Y[i])); } else { path.erase(minMaxPair(X[i], Y[i])); np.erase(minMaxPair(X[i], Y[i])); } std::shared_ptr<Paths> p1(new Paths), p2(new Paths); for(auto j : np) { p1->push_back(j); p2->push_back(revPath(N, j)); } while(now < (int)q.size() && q[now].first.first == i) { query1.push_back(make_pair(q[now].first.second, make_pair(q[now].second, p1))); query2.push_back(make_pair(N - 2 - q[now].first.second, make_pair(q[now].second, p2))); now++; } } for(auto i : solve(N, fixed1, query1)) ans[i.first] += i.second; for(auto i : solve(N, fixed2, query2)) ans[i.first] += i.second; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...