QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#331097#8055. Balanceucup-team296#WA 147ms3740kbC++205.7kb2024-02-18 00:07:222024-02-18 00:07:23

Judging History

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

  • [2024-02-18 00:07:23]
  • 评测
  • 测评结果：WA
  • 用时：147ms
  • 内存：3740kb
查看
  • [2024-02-18 00:07:22]
  • 提交

answer

#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

struct test {

    vector<int> e;
    vector<vector<int>> g;
    vector<int> tin;
    vector<int> up;
    vector<int> st;
    int cc = 0;
    vector<int> comp;
    int t = 0;

    void dfs(int x, int ee) {
        tin[x] = up[x] = t++;
        st.push_back(x);
        for (int i: g[x]) {
            if (i == (ee ^ 1)) continue;
            int y = e[i];
            if (tin[y] == -1) {
                dfs(y, i);
                if (up[y] > x) {
                    while (st.back() != y) {
                        comp[st.back()] = cc;
                        st.pop_back();
                    }
                    comp[y] = cc;
                    st.pop_back();
                    cc++;
                }
                up[x] = min(up[x], up[y]);
            } else {
                up[x] = min(up[x], tin[y]);
            }
        }
    }

    vector<int> sz;
    vector<vector<int>> gg;
    int k;
    vector<int> ps, ss;
    vector<int> mxp, mxs;

    void dfs_sz(int x, int p) {
        for (int y: gg[x]) {
            if (y == p) continue;
            dfs_sz(y, x);
            sz[x] += sz[y];
        }
    }

    vector<int> res;
    vector<int> vals;
    bool ok = false;

    void fill(int x, int v, int p) {
        res[x] = v;
        for (int y: gg[x]) {
            if (y == p) continue;
            fill(y, v, x);
        }
    }

    void fill_p(int x, int v, int p) {
        if (v == 0) return;
        if (sz[x] == ps[v - 1]) {
            v--;
        }
        res[x] = v;
        bool done = false;
        for (int y: gg[x]) {
            if (y == p) continue;
            if (mxp[y] == v && !done) {
                fill_p(y, v, x);
                done = true;
            } else {
                fill(y, v, x);
            }
        }
    }

    void fill_s(int x, int v, int p) {
        if (v == 0) return;
        if (sz[x] == ss[v - 1]) {
            v--;
        }
        res[x] = k - 1 - v;
        bool done = false;
        for (int y: gg[x]) {
            if (y == p) continue;
            if (mxs[y] == v && !done) {
                fill_s(y, v, x);
                done = true;
            } else {
                fill(y, k - 1 - v, x);
            }
        }
    }

    void print_ans() {
        cout << "Yes\n";
        for (int i = 0; i < (int)comp.size(); i++) {
            cout << vals[res[comp[i]]] << " ";
        }
        cout << "\n";
        ok = true;
    }

    void dfs2(int x, int p) {
        for (int y: gg[x]) {
            if (y == p) continue;
            dfs2(y, x);
            if (ok) return;
            mxp[x] = max(mxp[x], mxp[y]);
            mxs[x] = max(mxs[x], mxs[y]);
        }
        if (sz[x] == ps[mxp[x]]) mxp[x]++;
        if (sz[x] == ss[mxs[x]]) mxs[x]++;

        for (int _ = 0; _ < 2; _++) {
            int l = -1;
            int z = 0;
            for (int y: gg[x]) {
                if (y == p) continue;
                if (mxs[y] + z == k - 1) {
                    res.assign(res.size(), z);
                    fill_p(l, z, x);
                    fill_s(y, mxs[y], x);
                    print_ans();
                    return;
                }
                if (mxp[y] > z) {
                    z = mxp[y];
                    l = y;
                }
            }
            reverse(gg[x].begin(), gg[x].end());
        }
    }

    void solve() {
        int n, m;
        cin >> n >> m;
        e.resize(2 * m);
        g.resize(n);
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            e[2 * i] = y;
            g[x].push_back(2 * i);
            e[2 * i + 1] = x;
            g[y].push_back(2 * i + 1);
        }
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        tin.assign(n, -1);
        up.resize(n);
        comp.resize(n);
        dfs(0, -1);
        while (!st.empty()) {
            comp[st.back()] = cc;
            st.pop_back();
        }
        cc++;
//        for (int i = 0; i < n; i++) {
//            cout << comp[i] << " ";
//        }

        sz.resize(cc);
        gg.resize(cc);
        for (int i = 0; i < n; i++) {
            sz[comp[i]]++;
            for (int _: g[i]) {
                int j = e[_];
                if (comp[j] != comp[i]) {
                    gg[comp[i]].push_back(comp[j]);
                }
            }
        }
        dfs_sz(0, -1);

        sort(a.begin(), a.end());
        vector<pair<int, int>> st;
        for (int x: a) {
            if (!st.empty() && x == st.back().first) {
                st.back().second++;
            } else {
                st.push_back({x, 1});
            }
        }

        k = st.size();
        vector<int> c(k);
        vals.resize(k);
        for (int i = 0; i < k; i++) {
            c[i] = st[i].second;
            vals[i] = st[i].first;
        }

        ps.resize(k);
        ps[0] = c[0];
        for (int i = 1; i < k; i++) {
            ps[i] = ps[i - 1] + c[i];
        }

        ss.resize(k);
        ss[0] = c[k - 1];
        for (int i = 1; i < k; i++) {
            ss[i] = ss[i - 1] + c[k - 1 - i];
        }

        mxp.resize(cc);
        mxs.resize(cc);
        res.resize(cc);
        dfs2(0, -1);
        if (!ok) {
            cout << "No\n";
        }
    }
};

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        test().solve();
    }

    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
5 4 3 2 1 
No
Yes
2 2 1 3 2 
Yes
2 2 1 1 1 
No

result:

ok ok (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 147ms
memory: 3740kb

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
No
No
No
No
No
Yes
1 1 1 1 1 
No
Yes
1 1 1 
Yes
2 1 
Yes
1 1 1 1 1 
Yes
2 1 
No
No
Yes
1 1 1 
Yes
1 1 
No
No
No
No
Yes
1 1 
Yes
1 2 1 1 
No
No
No
Yes
1 1 
No
No
No
Yes
2 1 1 1 1 
Yes
2 1 1 1 
No
No
No
No
No
No
No
Yes
1 1 
Yes
2 2 1 
No
Yes
2 2 
No
...

result:

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

Server Time: 2024-12-02 21:42:56 | OpenSource Project