| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 766855 |
2023-06-26T08:14:24 Z |
birktj |
Werewolf (IOI18_werewolf) |
C++14 |
|
3182 ms |
195572 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
typedef vector<int> vi;
constexpr int MAXN = 2000000;
constexpr int INF = 1000000000;
template<class T, T e, class O>
class SegmentTree {
int N;
int off;
vector<T> v;
public:
SegmentTree(vector<T> initial) {
int n = initial.size();
N = 1;
while (N < n+2) N *= 2;
off = N+1;
N *= 2;
v = vector<T>(N, e);
for (int i = 0; i < n; i++)
v[off+i] = initial[i];
for (int i = off-1; i > 0; i--)
v[i] = O{}(v[i*2], v[i*2+1]);
}
T get(int l, int r) {
l += off-1;
r += off+1;
T lv = e;
T rv = e;
while (l/2 != r/2) {
if (l % 2 == 0) lv = O{}(lv, v[l+1]);
if (r % 2 == 1) rv = O{}(v[r-1], rv);
l /= 2;
r /= 2;
}
return O{}(lv, rv);
}
void update(int i, T n) {
i += off;
v[i] = n;
i /= 2;
while (i > 0) {
v[i] = O{}(v[i*2], v[i*2+1]);
i /= 2;
}
}
};
struct Min {
int operator() (int a, int b) {
return min(a, b);
}
};
struct Max {
int operator() (int a, int b) {
return max(a, b);
}
};
class UF {
vector<int> p;
public:
UF(int n) : p(n) {
for (int i = 0; i < n; i++)
p[i] = i;
}
int find(int i) {
return p[i] == i ? i : p[i] = find(p[i]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
p[b] = a;
}
};
int binary_search(function<bool(int)> P, int a, int b) {
while (a < b) {
int m = (a + b) / 2;
if (P(m)) b = m;
else a = m+1;
}
return a;
}
void euler_path(vi &out, vi G[], int LP[], int RP[], int u) {
LP[u] = out.size();
out.push_back(u);
//cerr << "visiting: " << u << endl;
for (int v : G[u]) {
euler_path(out, G, LP, RP, v);
out.push_back(u);
}
RP[u] = out.size() - 1;
}
int N, Q, SLP[MAXN], SRP[MAXN], ELP[MAXN], ERP[MAXN];
vi G[MAXN], ST[MAXN], ET[MAXN];
vector<int> check_validity(int n, vi x, vi y, vi S, vi E, vi L, vi R) {
N = n;
Q = S.size();
for (int i = 0; i < x.size(); i++) {
G[x[i]].push_back(y[i]);
G[y[i]].push_back(x[i]);
}
//cerr << "starting tree generation" << endl;
UF s_uf(n);
for (int i = n-1; i >= 0; i--) {
for (int j : G[i]) if (j > i && s_uf.find(i) != s_uf.find(j)) {
ST[i].push_back(s_uf.find(j));
s_uf.unite(i, j);
}
}
UF e_uf(n);
for (int i = 0; i < n; i++) {
for (int j : G[i]) if (j < i && e_uf.find(i) != e_uf.find(j)) {
ET[i].push_back(e_uf.find(j));
e_uf.unite(i, j);
}
}
//cerr << "starting euler_path" << endl;
vi s_seg;
vi e_seg;
euler_path(s_seg, ST, SLP, SRP, 0);
euler_path(e_seg, ET, ELP, ERP, n-1);
SegmentTree<int, INF, Min> s_tree(s_seg);
SegmentTree<int, 0, Max> e_tree(e_seg);
cerr << "s_seg: " << endl;
for (int x : s_seg)
cerr << x << " ";
cerr << endl;
cerr << "e_seg: " << endl;
for (int x : e_seg)
cerr << x << " ";
cerr << endl;
vi A(Q);
for (int i = 0; i < Q; i++) {
int s = S[i], e = E[i], l = L[i], r = R[i];
int s_l = binary_search([&](int i) {return s_tree.get(i, SLP[s]) >= l;}, 0, SLP[s]);
int s_r = binary_search([&](int i) {return s_tree.get(SRP[s], i) < l;}, SRP[s], s_seg.size()-1) - 1;
if (s_tree.get(SRP[s], s_r+1) >= l) s_r++;
int e_l = binary_search([&](int i) {return e_tree.get(i, ELP[e]) <= r;}, 0, ELP[e]);
int e_r = binary_search([&](int i) {return e_tree.get(ERP[e], i) > r;}, ERP[e], e_seg.size()-1) - 1;
if (e_tree.get(ERP[s], e_r+1) <= r) e_r++;
/*
cerr << "s = " << s << " e = " << e << " l = " << l << " r = " << r << endl;
cerr << "slp: " << SLP[s] << " srp: " << SRP[s] << endl;
cerr << "elp: " << ELP[e] << " erp: " << ERP[e] << endl;
//cerr << "s_tree.get(0, slp) = " << s_tree.get(0, SLP[s]) << endl;
cerr << "s_l = " << s_l << " s_r = " << s_r << endl;
cerr << "e_l = " << e_l << " e_r = " << e_r << endl;
*/
if (ELP[s_seg[s_l]] >= e_l && ERP[s_seg[s_r]] <= e_r)
A[i] = 1;
else if (SLP[e_seg[e_l]] >= s_l && SRP[e_seg[e_l]] <= s_r)
A[i] = 1;
else
A[i] = 0;
}
return A;
}
/*
int main() {
int n, m, q;
cin >> n >> m >> q;
vi x(m), y(m), s(q), e(q), l(q), r(q);
for (int i = 0; i < m; i++)
cin >> x[i] >> y[i];
for (int i = 0; i < q; i++)
cin >> s[i] >> e[i] >> l[i] >> r[i];
vi a = check_validity(n, x, y, s, e, l, r);
for (int i = 0; i < q; i++)
cout << a[i] << endl;
}
*/
Compilation message
werewolf.cpp: In function 'std::vector<int> check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
141192 KB |
Output is correct |
| 2 |
Incorrect |
57 ms |
141144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
141192 KB |
Output is correct |
| 2 |
Incorrect |
57 ms |
141144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3182 ms |
195572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
141192 KB |
Output is correct |
| 2 |
Incorrect |
57 ms |
141144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
