QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310024#8130. Yet Another Balanced Coloring Problemucup-team484#WA 23ms3600kbC++174.0kb2024-01-21 00:01:422024-01-21 00:01:42

Judging History

你现在查看的是最新测评结果

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-01-21 00:01:42]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:3600kb
  • [2024-01-21 00:01:42]
  • 提交

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)