QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#330680#8055. Balanceucup-team133#WA 231ms3852kbC++238.4kb2024-02-17 17:46:382024-02-17 17:46:39

Judging History

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

  • [2024-02-17 17:46:39]
  • 评测
  • 测评结果：WA
  • 用时：231ms
  • 内存：3852kb
查看
  • [2024-02-17 17:46:38]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

struct LowLink {
    int n, m = 0, t = 0, b = 0;
    std::vector<std::vector<int>> G;
    std::vector<std::pair<int, int>> es;
    std::vector<int> ord, low, tecc, bcc, tmp;
    std::vector<bool> is_articulation, is_bridge;

    LowLink(int n) : n(n), G(n), ord(n, -1), low(n), tecc(n, -1), is_articulation(n, false) {}

    void add_edge(int u, int v) {
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        G[u].emplace_back(m);
        G[v].emplace_back(m);
        es.emplace_back(u, v);
        is_bridge.emplace_back(false);
        bcc.emplace_back();
        m++;
    }

    void build() {
        for (int i = 0; i < n; i++) {
            if (ord[i] != -1) continue;
            dfs1(i, 0, -1);
            dfs2(i, -1);
        }
    }

    std::pair<int, int> operator[](int k) const { return es[k]; }

private:
    void dfs1(int v, int k, int pre) {
        ord[v] = k++, low[v] = ord[v];
        int cnt = 0;
        for (int& e : G[v]) {
            if (e == pre) continue;
            int u = es[e].first ^ es[e].second ^ v;
            if (ord[u] == -1) {
                cnt++;
                dfs1(u, k, e);
                low[v] = std::min(low[v], low[u]);
                if (pre != -1 and ord[v] <= low[u]) is_articulation[v] = true;
                if (ord[v] < low[u]) is_bridge[e] = true;
            } else
                low[v] = std::min(low[v], ord[u]);
        }
        if (pre == -1 and cnt > 1) is_articulation[v] = true;
    }

    void dfs2(int v, int pre) {
        if (pre == -1) tecc[v] = t++;
        for (int& e : G[v]) {
            if (e == pre) continue;
            int u = es[e].first ^ es[e].second ^ v;
            if (tecc[u] == -1 or ord[u] < ord[v]) tmp.emplace_back(e);
            if (tecc[u] >= 0) continue;
            if (ord[v] >= low[u])
                tecc[u] = tecc[v];
            else
                tecc[u] = t++;
            dfs2(u, e);
            if (ord[v] <= low[u]) {
                while (true) {
                    int ne = tmp.back();
                    tmp.pop_back();
                    bcc[ne] = b;
                    if (ne == e) break;
                }
                b++;
            }
        }
    }
};

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

void solve() {
    int n, m;
    cin >> n >> m;
    LowLink LL(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        LL.add_edge(--u, --v);
    }
    vector<int> a(n);
    cin >> a;

    sort(all(a));
    if (a.front() == a.back()) {
        cout << "Yes\n";
        cout << a << '\n';
        return;
    }
    LL.build();
    int N = LL.t;
    auto& tecc = LL.tecc;
    auto& is_bridge = LL.is_bridge;
    vector<vector<int>> G(N), group(N);
    for (int i = 0; i < m; i++) {
        if (not is_bridge[i]) continue;
        auto [u, v] = LL[i];
        u = tecc[u], v = tecc[v];
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    for (int i = 0; i < n; i++) group[tecc[i]].emplace_back(i);

    vector<int> sub(N);
    auto dfs_sz = [&](auto self, int v, int p) -> int {
        sub[v] = group[v].size();
        for (int& u : G[v]) {
            if (u == p) continue;
            sub[v] += self(self, u, v);
        }
        return sub[v];
    };
    auto dfs_search = [&](auto self, int v, int p, int mid) -> int {
        for (int& u : G[v]) {
            if (u == p) continue;
            if (sub[u] > mid) return self(self, u, v, mid);
        }
        return v;
    };
    int c = dfs_search(dfs_search, 0, -1, dfs_sz(dfs_sz, 0, -1) / 2);
    vector<int> cnt(n, 0);
    for (int& x : a) cnt[x - 1]++;

    int A = -1, B = -1;
    for (int i = 0, sum = 0; i < n; i++) {
        sum += cnt[i];
        if (A == -1 and sum >= (n + 1) / 2) A = i;
        if (B == -1 and (~n & 1) and sum >= (n + 2) / 2) B = i;
    }

    auto f = [&](int val) -> vector<int> {
        if (val == -1) return {};
        vector<vector<pair<int, int>>> route(2);
        for (int i = 0, sum = 0; i < val; i++) {
            if (cnt[i] == 0) continue;
            sum += cnt[i];
            route[0].emplace_back(sum, i);
        }
        for (int i = n - 1, sum = 0; i > val; i--) {
            if (cnt[i] == 0) continue;
            sum += cnt[i];
            route[1].emplace_back(sum, i);
        }
        vector nxt(N, vector<int>(2, -1));
        auto dfs = [&](auto self, int v, int p, const vector<pair<int, int>>& path, int idx) -> int {
            int maxi = 0;
            sub[v] = group[v].size();
            for (int& u : G[v]) {
                if (u == p) continue;
                if (nxt[v][idx] == -1) nxt[v][idx] = u;
                if (chmax(maxi, self(self, u, v, path, idx))) nxt[v][idx] = u;
                sub[v] += sub[u];
            }
            if (maxi < int(path.size()) and sub[v] == path[maxi].first) return maxi + 1;
            if (maxi < int(path.size()) and sub[v] > path[maxi].first) return -1;
            return maxi;
        };
        vector<vector<int>> ok(2);
        for (int& ch : G[c]) {
            for (int i = 0; i < 2; i++) {
                int res = dfs(dfs, ch, c, route[i], i);
                if (res == int(route[i].size())) ok[i].emplace_back(ch);
            }
        }
        // debug(c, val);
        // debug(route[0], route[1]);
        // debug(ok[0], ok[1]);
        int p = -1, q = -1;
        if (route[0].empty()) {
            if (not ok[1].empty()) q = ok[1][0];
        } else if (route[1].empty()) {
            if (not ok[0].empty()) p = ok[0][0];
        } else {
            for (int& u : ok[0]) {
                for (int& v : ok[1]) {
                    if (u != v) {
                        p = u, q = v;
                        break;
                    }
                }
                if (p != -1) break;
            }
        }
        if (p == -1 and q == -1) return {};
        // debug(val, p, q);
        vector<int> ans(n, -1);
        auto dfs2 = [&](auto self, int v, int p, int idx, bool on, int& cur,
                        const vector<pair<int, int>>& path) -> vector<int> {
            if (v == -1) return {};
            vector<int> tmp;
            for (int& vv : group[v]) tmp.emplace_back(vv);
            for (int& u : G[v]) {
                if (u == p) continue;
                auto ch = self(self, u, v, idx, on & (u == nxt[v][idx]), cur, path);
                if (tmp.size() < ch.size()) swap(tmp, ch);
                for (int& vv : ch) tmp.emplace_back(vv);
            }
            if (on and cur < int(path.size()) and sub[v] == path[cur].first) {
                assert(int(tmp.size()) == cnt[path[cur].second]);
                for (int& vv : tmp) ans[vv] = path[cur].second;
                tmp.clear();
                cur++;
            }
            return tmp;
        };
        int init = 0;
        dfs2(dfs2, p, c, 0, true, init, route[0]);
        assert(init == int(route[0].size()));
        init = 0;
        dfs2(dfs2, q, c, 1, true, init, route[1]);
        assert(init == int(route[1].size()));
        for (int i = 0; i < n; i++) {
            if (ans[i] == -1) {
                ans[i] = val;
            }
        }
        return ans;
    };

    for (int val : {A, B}) {
        auto ans = f(val);
        if (ans.empty()) continue;
        cout << "Yes\n";
        for (int i = 0; i < n; i++) cout << ans[i] + 1 << (i + 1 == n ? '\n' : ' ');
        return;
    }
    cout << "No\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (; T--;) solve();
    return 0;
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3852kb

input:

5
5 4
1 2
2 3
3 4
4 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 3 4 5
5 4
1 2
1 3
1 4
1 5
1 2 2 2 3
5 6
1 2
1 2
2 3
3 4
4 5
3 5
1 2 1 2 1
2 2
1 2
1 2
1 2

output:

Yes
1 2 3 4 5
No
Yes
2 1 3 2 2
Yes
2 2 1 1 1
No

result:

ok ok (5 test cases)

Test #2:

score: 0
Accepted
time: 154ms
memory: 3636kb

input:

100000
4 3
4 2
1 3
2 1
2 1 3 2
5 7
2 5
5 3
2 3
5 1
4 3
2 4
4 3
1 3 1 1 2
3 2
2 1
2 3
1 1 1
4 7
3 4
1 4
2 3
4 3
4 2
3 1
4 3
2 3 3 2
4 6
2 4
3 1
1 2
1 2
2 3
4 2
1 1 3 3
4 7
3 2
4 2
1 2
3 4
3 2
2 4
3 4
2 1 1 1
5 5
3 2
1 5
4 5
4 3
2 1
1 2 2 3 2
3 5
2 3
1 3
3 1
3 1
2 1
3 2 3
2 3
2 1
2 1
1 2
1 1
2 3
2 1
1...

output:

Yes
2 2 1 3
No
Yes
1 1 1
No
No
Yes
2 1 1 1
No
No
Yes
1 1
Yes
1 1
Yes
1 1
Yes
1 1 1 1
No
Yes
1 1 1 1 1
Yes
1 3 1 1 1
Yes
1 1 1
Yes
1 2
Yes
1 1 1 1 1
Yes
1 2
No
Yes
1 1
Yes
1 1 1
Yes
1 1
Yes
1 1 1 1
Yes
1 1
Yes
2 2 2 2 2
Yes
1 1 1 1 1
Yes
1 1
Yes
1 1 1 2
No
Yes
1 1
No
Yes
1 1
No
No
No
Yes
2 1 1 1 1
Ye...

result:

ok ok (100000 test cases)

Test #3:

score: 0
Accepted
time: 231ms
memory: 3700kb

input:

83335
9 17
1 4
8 9
5 2
1 3
2 7
1 7
2 8
6 7
2 4
1 8
5 8
7 1
8 6
4 6
4 7
6 9
7 9
7 3 4 4 7 4 2 4 8
6 9
3 1
1 2
3 5
1 2
3 4
4 5
6 3
6 1
6 2
4 3 2 2 1 3
9 8
9 3
5 7
5 9
2 6
1 8
4 1
4 2
4 3
4 2 5 3 4 5 4 5 4
6 7
2 1
1 5
6 1
3 1
6 5
2 4
5 3
2 1 2 1 2 1
4 6
2 1
4 2
1 4
1 2
1 4
3 1
2 2 4 2
6 10
2 3
3 5
2 1
...

output:

No
No
Yes
3 4 4 4 5 4 5 2 5
No
Yes
2 2 4 2
No
Yes
3 3 2 3
Yes
2 1 2
No
Yes
1 1 1 1 1
No
Yes
1 1 1
Yes
1 1 3 3 3
Yes
1 1
Yes
1 1
Yes
1 1 1 1
Yes
3 1 3
No
Yes
1 1 1 1 1 1 1 1
Yes
1 1 1 1 1 1 1
No
Yes
1 1
No
Yes
1 1 1 1 1
Yes
2 1 1 2 1
No
Yes
1 2 3 1 3 3 3 1
No
No
No
No
No
No
No
No
No
No
No
No
Yes
7 6 ...

result:

ok ok (83335 test cases)

Test #4:

score: -100
Wrong Answer
time: 230ms
memory: 3648kb

input:

58877
11 15
10 8
4 5
8 4
9 1
3 6
5 2
4 11
3 6
11 5
5 2
9 6
1 5
5 7
5 9
8 4
1 1 1 1 1 1 1 1 1 1 1
6 11
3 4
6 1
1 3
6 1
2 6
1 2
6 2
2 1
3 6
4 5
1 3
2 4 3 2 4 4
12 21
3 10
9 10
4 6
12 10
7 8
5 9
11 9
5 8
4 6
4 9
8 2
10 3
3 4
7 6
1 2
1 8
6 12
8 5
3 1
6 4
12 8
5 2 1 4 3 5 3 1 4 6 5 1
10 9
10 7
3 2
1 4
7 ...

output:

Yes
1 1 1 1 1 1 1 1 1 1 1
No
No
No
No
Yes
1 1
No
No
No
Yes
1 1 1 1
No
No
No
No
No
No
Yes
1 1 1 1 1
No
Yes
1 1 1 1
No
No
Yes
1 1 1 2 2
No
No
No
No
Yes
1 1 1 1 1 1 1 1 1 1 1 1 1
No
No
Yes
1 1 1
No
No
No
No
Yes
1 1
No
Yes
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
No
No
No
No
No
No
No
No
No
No
Yes
1 1
No
No
No
No
N...

result:

wrong answer ans finds an answer, but out doesn't (test case 16154)
English 繁體中文 简体中文

服务器时间: 2024-12-12 00:17:59 | 开源项目