QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309255#8130. Yet Another Balanced Coloring Problemucup-team1516#WA 22ms3832kbC++175.1kb2024-01-20 16:10:042024-01-20 16:10:05

Judging History

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

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-01-20 16:10:05]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:3832kb
  • [2024-01-20 16:10:04]
  • 提交

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>> g(n), r(m);

    for (int i = 0; i < n-1; ++i) {
        int x; cin >> x; x -= 1;
        g[x].push_back(i);
    }
    for (int i = 0; i < m-1; ++i) {
        int x; cin >> x; x -= 1;
        r[x].push_back(i);
    }
    int k = 0;
    for (int i = 0; i < n; ++i) {
        if (g[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 (g[s].size() == 0) {
                return vector<int>{s};
            }
            else if (g[s].size() == 1) {
                return dfs(dfs, g[s][0]);
            }
            else {
                vector<int> v;
                for (int t : g[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 (r[s].size() == 0) {
                return vector<int>{s};
            }
            else if (r[s].size() == 1) {
                return dfs(dfs, r[s][0]);
            }
            else {
                vector<int> v;
                for (int t : r[s]) {
                    auto rr = dfs(dfs, t);
                    rem2[s] += rr.size();
                    if (v.size() < rr.size()) swap(v, rr);
                    for (int &vv : rr) {
                        v.push_back(vv);
                    }
                }
                for (int t : v) {
                    v2[t].push_back(s);
                }
                rv2[s] = v;
                return v;
            }
        };
        dfs(dfs, m-1);
    }

    for (int i = 0; i < k; ++i) {
        if (col[i] != -1) continue;
        queue<int> q;
        auto psh = [&](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);
            }
            q.push(s);
        };
        col[i] = 0; psh(i); q.push(i);
        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) {
                                col[tt] = 1;
                            }
                            else {
                                col[tt] = 0;
                            }
                            psh(tt);
                        }
                    }
                }
                // NG
                if (v > c+1) {
                    cout << "IMPOSSIBLE" << "\n";
                    return;
                }
            }
            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) {
                                col[tt] = 1;
                            }
                            else {
                                col[tt] = 0;
                            }
                            psh(tt);
                        }
                    }
                }
                // NG
                if (v > c+1) {
                    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: 1ms
memory: 3832kb

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: -100
Wrong Answer
time: 22ms
memory: 3624kb

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
IMPOSSIBLE
BBR
IMPOSSIBLE
BBBRR
BBRR
IMPOSSIBLE
BBBBRRR
BBBBRRR
BRB
BRBBRR
BBR
IMPOSSIBLE
BBBRRR
IMPOSSIBLE
BBR
BBBRR
BBR
BBRRR
BBRBR
BRBR
BBBRR
BBR
BBRRB
BBRR
BBRRBR
BBBRRR
BRBR
BBBRRR
BBRBRR
BBBRR
BBBRRR
BBBRRR
IMPOSSIBLE
BRB
BBRR
BBR
BBR
BBBRR
BBRR
BBBRRR
BBR
BBRBR
BRR
BBBRRR
BBRRBR
BB...

result:

wrong answer jury has answer, participant doesn't (test case 3)