| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 592832 |
2022-07-09T16:31:32 Z |
Temmie |
Werewolf (IOI18_werewolf) |
C++17 |
|
383 ms |
524288 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
struct Dsu {
std::vector <int> p;
std::vector <int> cs;
inline Dsu(int s) {
cs.resize(s, 1);
p.resize(s);
std::iota(p.begin(), p.end(), 0);
}
inline Dsu(const Dsu& dsu) {
p = dsu.p;
cs = dsu.cs;
}
inline int find(int v) {
return v == p[v] ? v : (p[v] = find(p[v]));
}
inline void unite(int u, int v) {
u = find(u);
v = find(v);
if (cs[u] > cs[v]) {
p[v] = u;
cs[u] += cs[v];
} else {
p[u] = v;
cs[v] += cs[u];
}
}
friend std::ostream& operator << (std::ostream& stream, Dsu dsu) {
stream << "{ ";
for (int i = 0; i < (int) dsu.p.size(); i++) {
stream << dsu.find(i) << " ";
if (i + 1 == (int) dsu.p.size()) {
stream << "}";
}
}
return stream;
}
};
struct Block {
int from, to;
Dsu dsu;
std::vector <int> my_comp_to_main;
Block() : from(-1), to(-1), dsu(0), my_comp_to_main(0) { }
Block(int _from, int _to, const Dsu& _dsu) :
from(_from), to(_to), dsu(_dsu), my_comp_to_main(_dsu.p.size(), -1) { }
constexpr int idx_to_cdx(int ind) const {
return ind - from;
}
constexpr int cdx_to_ind(int cdx) const {
return cdx + from;
}
};
constexpr const int BS = 600;
struct Query {
int i, s, e, l, r;
};
std::vector <int> check_validity(int n, std::vector <int> _u, std::vector <int> _v,
std::vector <int> s, std::vector <int> e, std::vector <int> l, std::vector <int> r) {
int m = _u.size();
int q = s.size();
std::vector <std::vector <int>> g(n);
std::vector <int> deg(n, 0);
for (int i = 0; i < m; i++) {
g[_u[i]].push_back(_v[i]);
g[_v[i]].push_back(_u[i]);
deg[_u[i]]++;
deg[_v[i]]++;
}
int acu = 0;
std::vector <int> block_start;
for (int i = 0; i < n; i++) {
acu += deg[i];
if (acu >= BS) {
block_start.push_back(i);
acu = 0;
}
}
if (acu) {
block_start.push_back(n - 1);
}
std::vector <Block> blocks(block_start.size());
{
Dsu dsu(n);
for (int i = n - 1, bs_ptr = (int) block_start.size() - 1; bs_ptr >= 0 && i >= 0; i--) {
for (int x : g[i]) {
if (x >= i) {
dsu.unite(i, x);
}
}
if (block_start[bs_ptr] == i) {
blocks[bs_ptr] =
Block(bs_ptr ? block_start[bs_ptr - 1] + 1 : 0, block_start[bs_ptr], dsu);
bs_ptr--;
}
}
}
std::vector <std::vector <Query>> ques(n);
for (int i = 0; i < q; i++) {
ques[r[i]].push_back({ i, s[i], e[i], l[i], r[i] });
}
Dsu dsu(n);
std::vector <int> ans(q, 0);
for (int i = 0; i < n; i++) {
for (int x : g[i]) {
if (x <= i) {
dsu.unite(i, x);
int v = dsu.find(i);
for (Block& block : blocks) {
if (block.to > i) {
break;
}
block.my_comp_to_main[block.dsu.find(i)] = v;
block.my_comp_to_main[block.dsu.find(x)] = v;
}
}
}
for (const Query& que : ques[i]) {
assert(que.r == i);
int bid = std::lower_bound(blocks.begin(), blocks.end(), que.l,
[] (const Block& u, const int& v) { return u.to < v; }) - blocks.begin();
if (blocks[bid].my_comp_to_main[blocks[bid].dsu.find(que.s)] == dsu.find(que.e)) {
ans[que.i] = 1;
continue;
}
assert(blocks[bid].from <= que.s);
Dsu cdsu(blocks[bid].to - blocks[bid].from + 1);
std::vector <bool> cgood(blocks[bid].to - blocks[bid].from + 1, false);
std::vector <bool> cgood_s(blocks[bid].to - blocks[bid].from + 1, false);
for (int j = blocks[bid].to; j >= que.l; j--) {
if (dsu.find(j) == dsu.find(que.e)) {
cgood[cdsu.find(blocks[bid].idx_to_cdx(j))] = true;
}
for (int x : g[j]) {
if (x >= j) {
if (x <= blocks[bid].to && dsu.find(x) == dsu.find(que.e)) {
cgood[cdsu.find(blocks[bid].idx_to_cdx(x))] = true;
}
if (blocks[bid].my_comp_to_main[blocks[bid].dsu.find(x)] == dsu.find(que.e)) {
cgood[cdsu.find(blocks[bid].idx_to_cdx(j))] = true;
}
if (blocks[bid].dsu.find(que.s) == blocks[bid].dsu.find(x)) {
cgood_s[cdsu.find(blocks[bid].idx_to_cdx(j))] = true;
}
if (x <= blocks[bid].to) {
int u = cdsu.find(blocks[bid].idx_to_cdx(j));
int v = cdsu.find(blocks[bid].idx_to_cdx(x));
cgood[u] = cgood[v] = cgood[u] | cgood[v];
cgood_s[u] = cgood_s[v] = cgood_s[u] | cgood_s[v];
cdsu.unite(u, v);
}
}
}
}
for (int j = blocks[bid].to; j >= que.s; j--) {
if (cgood[cdsu.find(blocks[bid].idx_to_cdx(j))] &&
cgood_s[cdsu.find(blocks[bid].idx_to_cdx(j))]) {
ans[que.i] = 1;
break;
}
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
383 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
