제출 #439719

#제출 시각아이디문제언어결과실행 시간메모리
439719vulpes2Handcrafted Gift (IOI20_gift)C++17
15 / 100
442 ms94996 KiB
//#include <atcoder/maxflow.hpp> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #include <iostream> #include <map> #include <list> #include <set> #include <algorithm> #include <vector> #include <string> #include <functional> #include <queue> #include <deque> #include <stack> #include <unordered_map> #include <unordered_set> #include <cmath> #include <iterator> #include <random> #include <chrono> #include <complex> #include <bitset> #include <fstream> #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i) #define set_map_includes(set, elt) (set.find((elt)) != set.end()) #define readint(i) int i; cin >> i #define readll(i) ll i; cin >> i #define readdouble(i) double i; cin >> i #define readstring(s) string s; cin >> s typedef long long ll; //using namespace __gnu_pbds; //using namespace atcoder; using namespace std; //const ll modd = (1000LL * 1000LL * 1000LL + 7LL); const ll modd = 998244353; class UnionFind { public: vector<int> parent; vector<int> size; // size[i] = number of nodes in tree rooted at i // Note: not necessarily correct if i is not a root node map<int,set<int>> elts; UnionFind(int n) : parent(n), size(n) { forr(i,0,n) { parent[i] = i; size[i] = 1; elts[i].insert(i); } } int Find(int p) { int root = p; while (root != parent[root]) { root = parent[root]; } while (p != root) { int newp = parent[p]; parent[p] = root; p = newp; } return root; } void Union(int p, int q) { int rootP = Find(p); int rootQ = Find(q); if (rootP == rootQ) return; if (size[rootP] < size[rootQ]) { parent[rootP] = rootQ; size[rootQ] += size[rootP]; for(auto x : elts[rootP]) { elts[rootQ].insert(x); } elts.erase(rootP); } else { parent[rootQ] = rootP; size[rootP] += size[rootQ]; for(auto x : elts[rootQ]) { elts[rootP].insert(x); } elts.erase(rootQ); } } }; int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x); void craft(std::string &s); int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) { UnionFind uf(n); forr(i,0,r) { if (x[i]==2) { continue; } int l = a[i], r = b[i]; int curr = l; while (curr < r) { if (uf.Find(curr)!=uf.Find(curr+1)) { uf.Union(curr, curr+1); } else { curr = *prev(uf.elts[uf.Find(curr)].end()); } ++curr; } } bool problem = false; forr(i,0,r) { if (x[i]==1) { continue; } int l = a[i], r = b[i]; problem |= (uf.Find(l)==uf.Find(r)); } if (problem) { return 0; } std::string s(n, 'R'); char c = 'R'; for(auto x : uf.elts) { for(auto y : x.second) { s[y] = c; } c = (c=='R' ? 'B' : 'R'); } craft(s); return 1; }
#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...