| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1058799 |
2024-08-14T13:54:52 Z |
xnqs |
Werewolf (IOI18_werewolf) |
C++17 |
|
1600 ms |
39356 KB |
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include "werewolf.h"
enum NodeColorTypes {
White,
Black,
};
const int BLK_SIZE = 450;
struct MoQuery {
int src, dest;
int l, r;
int idx;
MoQuery():
src(0), dest(0), l(0), r(0), idx(0) {}
MoQuery(int src, int dest, int l, int r, int idx):
src(src), dest(dest), l(l), r(r), idx(idx) {}
bool operator < (const MoQuery& other) const {
if (this->l/BLK_SIZE!=other.l/BLK_SIZE) return this->l/BLK_SIZE < other.l/BLK_SIZE;
return this->r < other.r;
}
};
class DSURollback {
private:
struct DSUState {
int a, old_sz, b, old_t;
DSUState():
a(0), old_sz(0), b(0), old_t(0) {}
DSUState(int a, int old_sz, int b, int old_t):
a(a), old_sz(old_sz), b(b), old_t(old_t) {}
};
std::vector<int> t;
std::vector<int> sz;
std::vector<DSUState> stk;
public:
DSURollback(int n = 0) {
t.assign(n,0); std::iota(t.begin(),t.end(),0);
sz.assign(n,1);
}
int Find(int k) {
return ((t[k]==k) ? k : Find(t[k]));
}
int Unite(int a, int b) {
int ra = Find(a);
int rb = Find(b);
if (ra==rb) {
return 0;
}
stk.emplace_back(ra,sz[ra],rb,t[rb]);
sz[ra] += sz[rb];
t[rb] = ra;
return 1;
}
int Undo() {
if (stk.empty()) {
return 0;
}
auto [a, old_sz, b, old_t] = stk.back();
stk.pop_back();
sz[a] = old_sz;
t[b] = old_t;
return 1;
}
};
int gs, q;
std::vector<std::vector<int>> adj_list;
std::vector<MoQuery> queries_brute;
std::vector<MoQuery> queries_mo;
std::vector<int> ans;
// white (0..gs-1) -> black (gs..2*gs-1), black -> white
int Not(int k) {
return ((k<gs) ? k+gs : k-gs);
}
int node_color(int k) {
return ((k<gs) ? White : Black);
}
// handle black/white dsus separately and brute force check the virtual white->black edges between [l, r] in sqrt
void solve_brute_queries() {
std::sort(queries_brute.begin(),queries_brute.end(),[](const MoQuery& a, const MoQuery& b) {
return a.l > b.l;
});
DSURollback dsu_white(gs), dsu_black(gs);
std::vector<int> undos_black(gs+5,0);
std::vector<bool> activated_white(gs,0);
std::vector<bool> activated_black(gs+5,0);
int l = gs; // [l, oo]
int r = 0; // [-oo, r)
while (r<gs) {
for (const auto& i : adj_list[r]) {
// checking if i is white because white < gs
if (node_color(i)==White&&activated_black[i]) {
undos_black[r] += dsu_black.Unite(r,i);
}
}
activated_black[r] = 1;
++r;
#ifdef DBG
for (int i = 0; i < gs; i++) {
std::cout << undos_black[i] << " ";
}
std::cout << "\n";
#endif
}
for (auto [a, b, ql, qr, qidx] : queries_brute) {
// invariant: l = r
while (l>ql) {
--l;
for (const auto& i : adj_list[l]) {
if (node_color(i)==White&&activated_white[i]) {
dsu_white.Unite(l,i);
}
}
activated_white[l] = 1;
while (undos_black[r-1]>0) {
--undos_black[r-1];
dsu_black.Undo();
}
activated_black[r-1] = 0;
--r;
}
// increase r to qr+1
while (r<qr+1) {
for (const auto& i : adj_list[r]) {
// checking if i is white because white < gs
if (node_color(i)==White&&activated_black[i]) {
undos_black[r] += dsu_black.Unite(r,i);
}
}
activated_black[r] = 1;
++r;
}
// there is a virtual edge between white_i and black_i
for (int i = l; i < r; i++) {
if (dsu_white.Find(a)==dsu_white.Find(i)
&&dsu_black.Find(i)==dsu_black.Find(b)) {
ans[qidx] = 1;
}
}
// revert right pointer
while (r>l) {
while (undos_black[r-1]>0) {
--undos_black[r-1];
dsu_black.Undo();
}
activated_black[r-1] = 0;
--r;
}
}
}
void solve_mo_queries() {
std::sort(queries_mo.begin(),queries_mo.end());
int curr_blk = -1;
int l = -1, r = -1;
DSURollback dsu(2*gs);
std::vector<bool> activated;
for (auto [a, b, ql, qr, qidx] : queries_mo) {
if (ql/BLK_SIZE!=curr_blk) {
curr_blk = ql/BLK_SIZE;
l = (curr_blk+1)*BLK_SIZE;
r = l-1;
activated.assign(2*gs,0);
while (dsu.Undo());
// activate white nodes (human nodes [l, oo])
for (int i = l; i < gs; i++) {
for (const auto& j : adj_list[i]) {
if (activated[j]) {
dsu.Unite(i,j);
}
}
activated[i] = 1;
}
// activate black nodes (werewolf nodes [-oo, r])
for (int i = 0; i <= r; i++) {
for (const auto& j : adj_list[Not(i)]) {
if (activated[j]) {
dsu.Unite(Not(i),j);
}
}
activated[Not(i)] = 1;
}
}
// add werewolf nodes
while (r<qr) {
++r;
for (const auto& i : adj_list[Not(r)]) {
if (activated[i]) {
dsu.Unite(Not(r),i);
}
}
activated[Not(r)] = 1;
}
// add human nodes
int undos = 0;
while (l>ql) {
--l;
for (const auto& i : adj_list[l]) {
if (activated[i]) {
undos += dsu.Unite(l,i);
}
}
activated[l] = 1;
}
ans[qidx] = (dsu.Find(a)==dsu.Find(Not(b)));
// revert left pointer
while (l<(curr_blk+1)*BLK_SIZE) {
activated[l] = 0;
++l;
}
while (undos--) {
dsu.Undo();
}
}
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
gs = N;
q = static_cast<int>(S.size());
adj_list.assign(2*gs,std::vector<int>());
ans.assign(q,0);
for (int i = 0; i < static_cast<int>(X.size()); i++) {
adj_list[X[i]].emplace_back(Y[i]);
//adj_list[Y[i]].emplace_back(X[i]);
}
for (int i = 0; i < gs; i++) {
adj_list[i].emplace_back(Not(i));
//adj_list[Not(i)].emplace_back(i);
}
for (int i = 0; i < q; i++) {
int a = S[i];
int b = E[i];
int l = L[i];
int r = R[i];
if (l/BLK_SIZE==r/BLK_SIZE) {
queries_brute.emplace_back(a,b,l,r,i);
}
else {
//queries_brute.emplace_back(a,b,l,r,i);
queries_mo.emplace_back(a,b,l,r,i);
}
}
solve_brute_queries();
solve_mo_queries();
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1600 ms |
39356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
