QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#350906#8130. Yet Another Balanced Coloring ProblemCharizard2021WA 28ms3592kbC++172.3kb2024-03-11 09:42:002024-03-11 09:42:00

Judging History

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

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

answer

#include<bits/stdc++.h>
using namespace std;
struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }

	// get representive component (uses path compression)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

	bool same_set(int a, int b) { return get(a) == get(b); }

	int size(int x) { return -e[get(x)]; }

	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x;
		return true;
	}
};
int main(){
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        vector<int> p(n - 1);
        int k = n;
        for(int i = 0; i < n - 1; i++){
            cin >> p[i];
            p[i]--;
            k = min(k, p[i]);
        }
        vector<int> q(m - 1);
        for(int i = 0; i < m - 1; i++){
            cin >> q[i];
            q[i]--;
        }
        DSU dsu(k * 2);
        vector<int> thing(n, -1);
        for(int i = 0; i < k; i++){
            thing[i] = i;
        }
        for(int i = 0; i < n - 1; i++){
            if(thing[i] != -1){
                if(thing[p[i]] == -1){
                    thing[p[i]] = thing[i];
                }
                else{
                    int u = thing[i];
                    int v = thing[p[i]];
                    thing[v] = -1;
                    dsu.unite(2 * u, 2 * v + 1);
                    dsu.unite(2 * u + 1, 2 * v);
                }
            }
        }
        vector<int> thing2(m, -1);
        for(int i = 0; i < k; i++){
            thing2[i] = i;
        }
        for(int i = 0; i < m - 1; i++){
            if(thing2[i] != -1){
                if(thing2[q[i]] == -1){
                    thing2[q[i]] = thing2[i];
                }
                else{
                    int u = thing2[i];
                    int v = thing2[q[i]];
                    thing2[v] = -1;
                    dsu.unite(2 * u, 2 * v + 1);
                    dsu.unite(2 * u + 1, 2 * v);
                }
            }
        }
        for(int i = 0; i < k; i++){
            if(dsu.get(2 * i) % 2 == 1){
                cout << "R";
            }
            else{
                cout << "B";
            }
        }
        cout << "\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3484kb

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
RBB

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 28ms
memory: 3592kb

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:

BBBB
RRRRR
RRRRRR
BBB
BBBBB
RRRRR
RRRR
RRRR
BBBBBBB
BBBBBBB
BBB
BBBBBB
BRB
BBBBBBB
RRRRRR
BBBB
RBB
BBBBB
BBB
RBBBB
RRRRR
RRRR
BBBBB
BBB
RBBBB
BBBB
BBBBBB
BBBBBB
RRRR
BBBBBB
BBBBBB
BBBBB
BBBBBB
RBBBBB
BBBBBB
BBB
RRRR
BBB
BRB
BBBBB
RBBR
BBBBBB
BBB
RRRRR
RBB
RBBBBB
BBBBBB
BBB
BBBBBB
BBB
RBB
BBBB
BBBBB
...

result:

wrong answer charge of vertex 5 in tree 1 violates range (test case 1)