Submission #500339

#TimeUsernameProblemLanguageResultExecution timeMemory
500339600MihneaCollapse (JOI18_collapse)C++17
5 / 100
15092 ms6476 KiB
#include "collapse.h" #include <bits/stdc++.h> using namespace std; vector<int> brute(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) { int m = (int)t.size(); int q = (int)w.size(); for (int i = 0; i < m; i++) { if (x[i] > y[i]) { swap(x[i], y[i]); assert(0 <= x[i] && x[i] < y[i] && y[i] < n); } } assert((int) t.size() == m); assert((int) x.size() == m); assert((int) y.size() == m); assert((int) w.size() == q); assert((int) p.size() == q); vector<int> sol((int) w.size()); for (int iq = 0; iq < (int) w.size(); iq++) { set<pair<int, int>> s; for (int i = 0; i <= w[iq]; i++) { pair<int, int> cur = make_pair(x[i], y[i]); if (s.count(cur)) { s.erase(cur); } else { s.insert(cur); } } vector<pair<int, int>> ve; for (auto &it : s) { if (it.first <= p[iq] && it.second > p[iq]) { continue; } ve.push_back(it); } vector<int> t(n); iota(t.begin(), t.end(), 0); int comps = n; function<int(int)> getpap = [&] (int a) { if (t[a] == a) { return a; } else { return t[a] = getpap(t[a]); } }; function<void(int, int)> unite = [&] (int a, int b) { a = getpap(a); b = getpap(b); if (a != b) { comps--; t[a] = b; } }; for (auto &it : ve) { unite(it.first, it.second); } sol[iq] = comps; } return sol; } //const int edgeM = 333; const int edgeM = 7; vector<int> smart(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) { int m = (int)t.size(); int q = (int)w.size(); for (int i = 0; i < m; i++) { if (x[i] > y[i]) { swap(x[i], y[i]); assert(0 <= x[i] && x[i] < y[i] && y[i] < n); } } function<bool(int, int)> cmp = [&] (int i, int j) { return y[i] < y[j]; }; assert((int) t.size() == m); assert((int) x.size() == m); assert((int) y.size() == m); assert((int) w.size() == q); assert((int) p.size() == q); vector<int> sol((int) w.size()); for (int ISTEP = 1; ISTEP <= 2; ISTEP++) { vector<int> edgeBucket(m), edgeFirst(m), edgeLast(m); for (int i = 0; i < m; i++) { edgeBucket[i] = i / edgeM; edgeLast[edgeBucket[i]] = i; } for (int i = m - 1; i >= 0; i--) { edgeFirst[edgeBucket[i]] = i; } vector<vector<int>> inds(m); for (int i = 0; i < q; i++) { inds[w[i]].push_back(i); } set<pair<int, int>> s; for (int edgeBucketId = edgeBucket[0]; edgeBucketId <= edgeBucket[m - 1]; edgeBucketId++) { vector<int> guys; for (int step = edgeFirst[edgeBucketId]; step <= edgeLast[edgeBucketId]; step++) { for (auto &iq : inds[step]) { guys.push_back(iq); } } sort(guys.begin(), guys.end(), cmp); set<pair<int, int>> cop = s; for (auto &iq : guys) { s = cop; for (int step = edgeFirst[edgeBucketId]; step <= w[iq]; step++) { pair<int, int> cur = make_pair(x[step], y[step]); if (s.count(cur)) { s.erase(cur); } else { s.insert(cur); } } vector<pair<int, int>> ve; for (auto &it : s) { if (it.second <= p[iq]) { ve.push_back(it); continue; } } vector<int> t(n); iota(t.begin(), t.end(), 0); int comps = p[iq] + 1; function<int(int)> getpap = [&] (int a) { if (t[a] == a) { return a; } else { return t[a] = getpap(t[a]); } }; function<void(int, int)> unite = [&] (int a, int b) { a = getpap(a); b = getpap(b); if (a != b) { comps--; t[a] = b; } }; for (auto &it : ve) { unite(it.first, it.second); } sol[iq] += comps; } s = cop; for (int step = edgeFirst[edgeBucketId]; step <= edgeLast[edgeBucketId]; step++) { pair<int, int> cur = make_pair(x[step], y[step]); if (s.count(cur)) { s.erase(cur); } else { s.insert(cur); } } } for (int i = 0; i < m; i++) { swap(x[i], y[i]); x[i] = n - 1 - x[i]; y[i] = n - 1 - y[i]; } for (int i = 0; i < q; i++) { p[i] = n - 2 - p[i]; } } return sol; } vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) { auto B=brute(N,T,X,Y,W,P); auto S=smart(N,T,X,Y,W,P); assert(B==S); return S; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...