QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #309365 | #8130. Yet Another Balanced Coloring Problem | ucup-team1516# | TL | 27ms | 3704kb | C++17 | 8.3kb | 2024-01-20 16:54:52 | 2024-01-20 16:54:52 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
inline double time() {
return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}
void slv() {
int n,m; cin >> n >> m;
vector<vector<int>> g1(n), g2(m);
for (int i = 0; i < n-1; ++i) {
int x; cin >> x; x -= 1;
g1[x].push_back(i);
}
for (int i = 0; i < m-1; ++i) {
int x; cin >> x; x -= 1;
g2[x].push_back(i);
}
int k = 0;
for (int i = 0; i < n; ++i) {
if (g1[i].size() == 0) k += 1;
}
vector<int> col(k, -1);
vector<vector<int>> v1(k), v2(k);
vector<vector<int>> rv1(n), rv2(m);
vector<int> rem1(n), rem2(m);
vector<int> val1(n), val2(m);
{
auto dfs = [&](auto dfs, int s) -> vector<int> {
if (g1[s].size() == 0) {
return vector<int>{s};
}
else if (g1[s].size() == 1) {
return dfs(dfs, g1[s][0]);
}
else {
vector<int> v;
for (int t : g1[s]) {
auto r = dfs(dfs, t);
rem1[s] += r.size();
if (v.size() < r.size()) swap(v, r);
for (int &vv : r) {
v.push_back(vv);
}
}
for (int t : v) {
v1[t].push_back(s);
}
rv1[s] = v;
return v;
}
};
dfs(dfs, n-1);
}
{
auto dfs = [&](auto dfs, int s) -> vector<int> {
if (g2[s].size() == 0) {
return vector<int>{s};
}
else if (g2[s].size() == 1) {
return dfs(dfs, g2[s][0]);
}
else {
vector<int> v;
for (int t : g2[s]) {
auto r = dfs(dfs, t);
rem2[s] += r.size();
if (v.size() < r.size()) swap(v, r);
for (int &vv : r) {
v.push_back(vv);
}
}
for (int t : v) {
v2[t].push_back(s);
}
rv2[s] = v;
return v;
}
};
dfs(dfs, m-1);
}
auto set = [&](int s, int c) -> void {
col[s] = c;
for (int &t : v1[s]) {
rem1[t] -= 1;
val1[t] += (col[s] == 0 ? 1 : -1);
}
for (int &t : v2[s]) {
rem2[t] -= 1;
val2[t] += (col[s] == 0 ? 1 : -1);
}
};
auto unset = [&](int s) -> void {
for (int &t : v1[s]) {
rem1[t] += 1;
val1[t] -= (col[s] == 0 ? 1 : -1);
}
for (int &t : v2[s]) {
rem2[t] += 1;
val2[t] -= (col[s] == 0 ? 1 : -1);
}
col[s] = -1;
};
vector<int> op;
auto dfs = [&](auto dfs, int i) -> bool {
if (op.size() == k) return true;
if (col[i] != -1) return dfs(dfs, i+1);
queue<int> q;
// 0で塗る
{
set(i, 0); q.push(i); op.push_back(i);
bool ok = true;
while (q.size()) {
int s = q.front(); q.pop();
for (int &t : v1[s]) {
int v = abs(val1[t]);
int c = rem1[t];
// 確定
if (v == c or v == c+1) {
if (c == 0) continue;
for (int &tt : rv1[t]) {
if (col[tt] == -1) {
if (val1[t] > 0) {
set(tt, 1); q.push(tt); op.push_back(tt);
}
else {
set(tt, 0); q.push(tt); op.push_back(tt);
}
}
}
}
// NG
if (v > c+1) {
ok = false;
break;
}
}
for (int &t : v2[s]) {
int v = abs(val2[t]);
int c = rem2[t];
// 確定
if (v == c or v == c+1) {
if (c == 0) continue;
for (int &tt : rv2[t]) {
if (col[tt] == -1) {
if (val2[t] > 0) {
set(tt, 1); q.push(tt); op.push_back(tt);
}
else {
set(tt, 0); q.push(tt); op.push_back(tt);
}
}
}
}
// NG
if (v > c+1) {
ok = false;
break;
}
}
}
if (ok and dfs(dfs, i+1)) return true;
while (1) {
int s = op.back();
unset(s); op.pop_back();
if (s == i) break;
}
}
// 1で塗る
{
set(i, 1); q.push(i); op.push_back(i);
bool ok = true;
while (q.size()) {
int s = q.front(); q.pop();
for (int &t : v1[s]) {
int v = abs(val1[t]);
int c = rem1[t];
// 確定
if (v == c or v == c+1) {
if (c == 0) continue;
for (int &tt : rv1[t]) {
if (col[tt] == -1) {
if (val1[t] > 0) {
set(tt, 1); q.push(tt); op.push_back(tt);
}
else {
set(tt, 0); q.push(tt); op.push_back(tt);
}
}
}
}
// NG
if (v > c+1) {
ok = false;
break;
}
}
for (int &t : v2[s]) {
int v = abs(val2[t]);
int c = rem2[t];
// 確定
if (v == c or v == c+1) {
if (c == 0) continue;
for (int &tt : rv2[t]) {
if (col[tt] == -1) {
if (val2[t] > 0) {
set(tt, 1); q.push(tt); op.push_back(tt);
}
else {
set(tt, 0); q.push(tt); op.push_back(tt);
}
}
}
}
// NG
if (v > c+1) {
ok = false;
break;
}
}
}
if (ok and dfs(dfs, i+1)) return true;
while (1) {
int s = op.back();
unset(s); op.pop_back();
if (s == i) break;
}
}
return false;
};
dfs(dfs, 0);
if (op.size() != k) {
cout << "IMPOSSIBLE" << "\n";
return;
}
for (int i = 0; i < k; ++i) {
if (col[i] == 0) cout << "B";
else if (col[i] == 1) cout << "R";
else cout << "?";
}
cout << "\n";
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int q; cin >> q;
while (q--) {
slv();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3704kb
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 BRB
result:
ok ok (2 test cases)
Test #2:
score: 0
Accepted
time: 27ms
memory: 3688kb
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 BBBRR BRBBRR BBR BBRBR BBBRR BBRR BRBR BBBBRRR BBBBRRR BRB BRBBRR BBR BBBRBRR BBBRRR BRBR BBR BBBRR BBR BBRRR BBRBR BRBR BBBRR BBR BBRRB BBRR BBRRBR BBBRRR BRBR BBBRRR BBRBRR BBBRR BBBRRR BBBRRR BBRRBR BRB BBRR BBR BBR BBBRR BBRR BBBRRR BBR BBRBR BRR BBBRRR BBRRBR BBR BBBRRR BBR BRR BBRR BRBBR ...
result:
ok ok (10000 test cases)
Test #3:
score: -100
Time Limit Exceeded
input:
1000 98 96 41 39 52 47 34 37 45 33 68 54 74 35 65 58 49 46 53 42 87 30 43 48 38 36 56 40 88 66 32 31 72 44 91 96 51 85 83 61 60 59 80 63 70 80 75 61 51 83 50 69 86 55 79 62 67 57 73 93 96 64 69 91 78 73 80 83 81 91 91 71 76 81 75 90 92 77 82 89 82 86 98 84 96 89 97 96 91 97 94 93 95 97 97 95 96 97 9...