QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310024 | #8130. Yet Another Balanced Coloring Problem | ucup-team484# | WA | 23ms | 3600kb | C++17 | 4.0kb | 2024-01-21 00:01:42 | 2024-01-21 00:01:42 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
struct segment_tree {
struct data {
int mn = mod, mx = -mod;
};
struct operation {
int lz = 0;
};
static data combine(data dl, data dr) {
return data{min(dl.mn, dr.mn), max(dl.mx, dr.mx)};
};
static data calculate(operation o, data d) {
return data{o.lz + d.mn, o.lz + d.mx};
};
static operation merge(operation ot, operation ob) {
return operation{ot.lz + ob.lz};
};
int n, h;
vector<data> t;
vector<operation> o;
segment_tree(int n = 0) : n(n), h(32 - __builtin_clz(n)), t(2 * n), o(n) {}
segment_tree(vector<data> & a) : segment_tree(a.size()) {
for (int i = 0; i < n; i++)
t[i + n] = a[i];
for (int x = n - 1; x > 0; x--)
t[x] = combine(t[x << 1], t[x << 1 | 1]);
}
void apply(int x, operation op) {
t[x] = calculate(op, t[x]);
if (x < n)
o[x] = merge(op, o[x]);
}
void push(int x) {
for (int s = h; s > 0; s--) {
int c = x >> s;
apply(c << 1, o[c]);
apply(c << 1 | 1, o[c]);
o[c] = operation();
}
}
void build(int x) {
while (x >>= 1)
t[x] = calculate(o[x], combine(t[x << 1], t[x << 1 | 1]));
}
// set the data at the position i
void setValue(int i, data d) {
i += n;
push(i);
t[i] = d;
build(i);
}
// query the data on the range [l, r[
data query(int l, int r) {
l += n; r += n;
push(l); push(r - 1);
data dl, dr;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1)
dl = combine(dl, t[l++]);
if (r & 1)
dr = combine(t[--r], dr);
}
return combine(dl, dr);
}
// apply an operation on the range [l, r[
void apply(int l, int r, operation op) {
l += n; r += n;
push(l); push(r - 1);
int xl = l, xr = r;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1)
apply(l++, op);
if (r & 1)
apply(--r, op);
}
build(xl); build(xr - 1);
}
};
struct dat {
int n, idx = 0;
vector<int> par, head, pos;
vector<vector<int>> adj;
segment_tree seg;
dat(int n = 0) : n(n), par(n, -1), adj(n), head(n), pos(n), seg(n) {}
int dfs(int u) {
int r = 1, mx = 0;
for (int i = 0; i < size(adj[u]); i++) {
int v = adj[u][i];
int s = dfs(v);
if (s > mx) {
mx = s;
swap(adj[u][i], adj[u][0]);
}
r += s;
}
return r;
}
int dfs2(int u) {
pos[u] = idx++;
int r = size(adj[u]) == 0 ? 1 : 0;
for (int i = 0; i < size(adj[u]); i++) {
int v = adj[u][i];
if (i > 0)
head[v] = v;
else
head[v] = head[u];
r += dfs2(v);
}
seg.setValue(pos[u], segment_tree::data{r, r});
return r;
}
void build() {
dfs(n - 1);
head[n - 1] = n - 1;
dfs2(n - 1);
}
int can(int i) {
int f = 0, ok = 1;
while (i != -1) {
auto dat = seg.query(pos[head[i]], pos[i] + 1);
ok &= dat.mn >= 1;
f |= dat.mx > 1;
i = par[head[i]];
}
return ok == 1 && f == 1;
}
void flip(int i) {
while (i != -1) {
seg.apply(pos[head[i]], pos[i] + 1, segment_tree::operation{-2});
i = par[head[i]];
}
}
int valid() {
auto dat = seg.query(0, n);
return -1 <= dat.mn && dat.mx <= 1;
}
};
void solve() {
int n, m, k = N; cin >> n >> m;
dat t1(n), t2(m);
for (int i = 0; i + 1 < n; i++) {
int p; cin >> p; p--;
k = min(k, p);
t1.par[i] = p;
t1.adj[p].push_back(i);
}
for (int i = 0; i + 1 < m; i++) {
int p; cin >> p; p--;
t2.par[i] = p;
t2.adj[p].push_back(i);
}
t1.build();
t2.build();
string s(k, 'R');
for (int i = 0; i < k; i++) {
if (!t1.can(i) || !t2.can(i))
continue;
s[i] = 'B';
t1.flip(i);
t2.flip(i);
}
if (t1.valid() && t2.valid())
cout << s << "\n";
else
cout << "IMPOSSIBLE\n";
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int t; cin >> t; while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3492kb
input:
2 7 7 5 5 6 6 7 7 5 6 5 6 7 7 5 4 4 4 5 5 4 4 4
output:
BRRB BRR
result:
ok ok (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 23ms
memory: 3600kb
input:
10000 6 6 5 5 5 5 6 5 6 6 6 6 9 6 7 9 7 7 6 8 9 9 6 6 6 6 6 9 8 9 9 8 7 7 8 8 9 7 7 8 7 7 7 8 6 10 4 5 5 6 6 4 6 5 7 8 9 8 9 10 6 9 6 6 6 6 6 6 9 7 8 8 9 9 9 8 9 8 6 6 7 6 7 8 7 9 7 6 7 8 9 9 9 8 6 7 7 5 8 8 8 9 7 5 6 5 8 7 8 8 7 6 6 5 5 6 7 8 5 7 6 6 7 7 9 9 8 9 8 8 8 8 9 9 9 9 8 8 9 9 8 9 9 8 8 8 ...
output:
BBRR BBRRR IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE BBRR IMPOSSIBLE BBBRRRR BBBRRRR IMPOSSIBLE BRBBRR IMPOSSIBLE IMPOSSIBLE BBBRRR IMPOSSIBLE BRR BBRRR IMPOSSIBLE BBRRR IMPOSSIBLE BRBR BBRRR IMPOSSIBLE BBRRR BBRR BBRRBR BBBRRR BRBR BBBRRR BBRBRR IMPOSSIBLE BBBRRR BBBRRR IMPOSSIBLE BRR BBRR BRR IM...
result:
wrong answer jury has answer, participant doesn't (test case 3)