QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#330786#8055. Balanceucup-team1191#Compile Error//C++2011.1kb2024-02-17 19:04:352024-02-17 19:04:35

Judging History

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

  • [2024-02-17 19:04:35]
  • 评测
  • [2024-02-17 19:04:35]
  • 提交

answer

/*
    author:  Maksim1744
    created: 17.02.2024 13:22:03
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
// auto gcd = std::y_combinator([](auto gcd, int a, int b) -> int {
//     return b == 0 ? a : gcd(b, a % b);
// });

struct DSU {
    vector<int> rk;
    vector<int> p;
    int n;

    DSU(int n = 1) : n(n) {
        reset(n);
    }

    void reset(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        rk.assign(n, 1);
    }

    int par(int v) {
        return v == p[v] ? v : p[v] = par(p[v]);
    }

    bool un(int u, int v) {
        u = par(u);
        v = par(v);
        if (u == v) return false;
        if (rk[u] > rk[v]) swap(u, v);
        p[u] = v;
        rk[v] += rk[u];
        return true;
    }

    bool check(int u, int v) {
        return par(u) == par(v);
    }
};

void test_case(int test) {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> e(m);
    cin >> e;
    --e;
    vector<int> a(n);
    cin >> a;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        g[e[i].first].pb(i);
        g[e[i].second].pb(i);
    }

    if (count(a.begin(), a.end(), a[0]) == n) {
        cout << "Yes\n";
        cout << a << '\n';
        return;
    }

    vector<bool> u(n, false);
    vector<int> level(n, 0);
    vector<int> up(n, 1e9);
    vector<int> bridges;
    vector<bool> is_bridge(m, false);
    y_combinator([&](auto dfs, int v, int pi) -> void {
        u[v] = true;
        for (int ei : g[v]) {
            if (ei == pi) continue;
            int k = e[ei].first ^ e[ei].second ^ v;
            if (u[k]) {
                up[v] = min(up[v], level[k]);
            } else {
                level[k] = level[v] + 1;
                dfs(k, ei);
                if (up[k] > level[v]) {
                    bridges.pb(ei);
                    is_bridge[ei] = true;
                }
                up[v] = min(up[v], up[k]);
            }
        }
    })(0, -1);

    DSU d(n);
    for (int i = 0; i < m; ++i) {
        if (is_bridge[i]) continue;
        d.un(e[i].first, e[i].second);
    }
    vector<int> pars;
    for (int i = 0; i < n; ++i) {
        pars.pb(d.par(i));
    }
    sort(pars.begin(), pars.end());
    pars.erase(unique(pars.begin(), pars.end()), pars.end());

    vector<vector<int>> tree(pars.size());
    vector<int> w(pars.size(), 0);
    for (int i = 0; i < n; ++i)
        w[lowb(pars, d.par(i))]++;
    for (int ei : bridges) {
        auto [u, v] = e[ei];
        u = lowb(pars, d.par(u));
        v = lowb(pars, d.par(v));
        tree[u].pb(v);
        tree[v].pb(u);
    }

    show(bridges);

    vector<int> x = a;
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    vector<int> wa(x.size(), 0);
    {
        map<int, int> mm;
        for (int u : a)
            mm[u]++;
        for (int i = 0; i < wa.size(); ++i) {
            wa[i] = mm[x[i]];
        }
    }

    vector<int> pref_to(n, -1);
    vector<int> suf_to(n, -1);
    vector<int> par(n, -1);
    vector<int> sz(n, 0);

    vector<int> pref_wa = wa;
    for (int i = 1; i < pref_wa.size(); ++i)
        pref_wa[i] += pref_wa[i - 1];

    vector<pair<int, int>> ans_path;

    show(tree);

    y_combinator([&](auto dfs, int v, int p) -> pair<int, int> {
        par[v] = p;
        if (!ans_path.empty()) return {-1, -1};
        int best_pref = -1;
        int best_suf = wa.size() - 1;
        sz[v] = w[v];

        for (int k : tree[v]) {
            if (k == p) continue;
            auto [cur_pref, cur_suf] = dfs(k, v);
            if (!ans_path.empty()) break;
            sz[v] += sz[k];
            bool had_pref = false;
            bool had_suf = false;
            if (cur_pref + 2 < wa.size()) {
                if (sz[k] == pref_wa[cur_pref + 1]) {
                    had_pref = true;
                    ++cur_pref;
                }
            }
            if (cur_suf > 0) {
                if (sz[k] == n - pref_wa[cur_suf - 1]) {
                    had_suf = true;
                    --cur_suf;
                }
            }

            if (best_pref + 1 == cur_suf) {
                show(v, k);
                show(best_pref, best_suf);
                show(cur_pref, cur_suf);
                show(had_pref, had_suf);
                show(pref_to, suf_to);
                int vert = v;
                for (int i = 0; i <= best_pref; ++i) {
                    vert = pref_to[vert];
                    ans_path.eb(vert, par[vert]);
                }
                vert = k;
                if (had_suf) {
                    ans_path.eb(k, v);
                    ++cur_suf;
                }
                for (int i = 0; i < wa.size() - cur_suf - 1; ++i) {
                    vert = suf_to[vert];
                    ans_path.eb(vert, par[vert]);
                }
                assert(ans_path.size() + 1 == wa.size());
                break;
            }

            if (cur_pref + 1 == best_suf) {
                show(v, k);
                show(best_pref, best_suf);
                show(cur_pref, cur_suf);
                show(had_pref, had_suf);
                show(pref_to, suf_to);
                int vert = k;
                if (had_pref) {
                    ans_path.eb(k, v);
                    --cur_pref;
                }
                for (int i = 0; i <= cur_pref; ++i) {
                    vert = pref_to[vert];
                    ans_path.eb(vert, par[vert]);
                }
                vert = v;
                for (int i = 0; i < wa.size() - best_suf - 1; ++i) {
                    vert = suf_to[vert];
                    ans_path.eb(vert, par[vert]);
                }
                assert(ans_path.size() + 1 == wa.size());
                break;
            }

            if (cur_pref > best_pref) {
                best_pref = cur_pref;
                pref_to[v] = (had_pref ? k : pref_to[k]);
            }
            if (cur_suf < best_suf) {
                best_suf = cur_suf;
                suf_to[v] = (had_suf ? k : suf_to[k]);
            }
        }
        return {best_pref, best_suf};
    })(0, -1);

    if (ans_path.empty()) {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";

    DSU d2(tree.size());
    set<pair<int, int>> sans(ans_path.begin(), ans_path.end());
    for (int i = 0; i < tree.size(); ++i) {
        for (int j : tree[i]) {
            if (sans.count({i, j}) || sans.count({j, i})) continue;
            d2.un(i, j);
        }
    }
    vector<int> par2;
    for (int i = 0; i < tree.size(); ++i) {
        par2.pb(d2.par(i));
    }
    sort(par2.begin(), par2.end());
    par2.erase(unique(par2.begin(), par2.end()), par2.end());

    show(par2);

    vector<vector<int>> bamb(par2.size());
    for (auto [u, v] : ans_path) {
        u = lowb(par2, d2.par(u));
        v = lowb(par2, d2.par(v));
        bamb[u].pb(v);
        bamb[v].pb(u);
    }
    show(bamb);
    int leaf = 0;
    while (bamb[leaf].size() != 1)
        ++leaf;
    vector<int> szs_0(par2.size());
    for (int i = 0; i < tree.size(); ++i) {
        szs_0[lowb(par2, d2.par(i))] += w[i];
    }
    show(leaf);

    vector<int> ord;
    y_combinator([&](auto dfs, int v, int p) -> void {
        ord.pb(v);
        for (int k : bamb[v]) {
            if (k != p) {
                dfs(k, v);
            }
        }
    })(leaf, -1);

    assert(ord.size() == bamb.size());
    vector<int> szs;
    for (int i : ord)
        szs.pb(szs_0[i]);
    if (szs != wa) {
        reverse(ord.begin(), ord.end());
        reverse(szs.begin(), szs.end());
    }
    assert(szs == wa);

    show(ord);

    vector<vector<int>> who(ord.size());
    show(pars);
    show(par2);
    for (int i = 0; i < n; ++i) {
        show(i, d.par(i));
        who[lowb(par2, d2.par(lowb(pars, d.par(i))))].pb(i);
    }
    show(who);
    vector<int> ans(n, -1);
    for (int i = 0; i < who.size(); ++i) {
        assert(who[ord[i]].size() == wa[i]);
        for (int j : who[ord[i]])
            ans[j] = x[i];
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T;
    cin >> T;
    for (int test = 1; test <= T; ++test) {
        test_case(test);
    }

    return 0;
}

詳細信息

answer.code: In instantiation of ‘std::istream& operator>>(std::istream&, std::vector<_Tp>&) [with T = std::pair<int, int>; std::istream = std::basic_istream<char>]’:
answer.code:110:12:   required from here
answer.code:29:103: error: no match for ‘operator>>’ (operand types are ‘std::istream’ {aka ‘std::basic_istream<char>’} and ‘std::pair<int, int>’)
   29 | template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
      |                                                                                                    ~~~^~~~
In file included from /usr/include/c++/13/sstream:40,
                 from /usr/include/c++/13/complex:45,
                 from /usr/include/c++/13/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127,
                 from answer.code:6:
/usr/include/c++/13/istream:325:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
  325 |       operator>>(void*& __p)
      |       ^~~~~~~~
/usr/include/c++/13/istream:325:25: note:   no known conversion for argument 1 from ‘std::pair<int, int>’ to ‘void*&’
  325 |       operator>>(void*& __p)
      |                  ~~~~~~~^~~
/usr/include/c++/13/istream:224:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
  224 |       operator>>(long double& __f)
      |       ^~~~~~~~
/usr/include/c++/13/istream:224:31: note:   no known conversion for argument 1 from ‘std::pair<int, int>’ to ‘long double&’
  224 |       operator>>(long double& __f)
      |                  ~~~~~~~~~~~~~^~~
/usr/include/c++/13/istream:220:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
  220 |       operator>>(double& __f)
      |       ^~~~~~~~
/usr/include/c++/13/istream:220:26: note:   no known conversion for argument 1 from ‘std::pair<int, int>’ to ‘double&’
  220 |       operator>>(double& __f)
      |                  ~~~~~~~~^~~
/usr/include/c++/13/istream:216:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
  216 |       operator>>(float& __f)
      |       ^~~~~~~~
/usr/include/c++/13/istream:216:25: note:   no known conversion for argument 1 from ‘std::pair<int, int>’ to ‘float&’
  216 |       operator>>(float& __f)
      |                  ~~~~~~~^~~
/usr/include/c++/13/istream:201:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
  201 |       operator>>(unsigned long long& __n)
      |       ^~~~~~~~
/usr/include/c++/13/istream:201:38: note:   no known conversion for argument 1 from ‘std::pair<int, int>’ to ‘long long unsigned int&’
  201 |       operator>>(unsigned long long& __n)
      |                  ~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/istream:197:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
  197 |       operator>>(long long& __n)
      |       ^~~~~~~~
/usr/include/c++/13/istream:197:29: note:   no known conversion for argument 1 from ‘std::pair<int, int>’ to ‘long long int&’
  197 |       operator>>(long long& __n)
      |                  ~~~~~~~~~~~^~~
/usr/include/c++/13/istream:192:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
  192 |       operator>>(unsigned long& __n)
      |       ^~~~~~~~
/usr/include/c++/13/istream:192:33: note:   no known conversion for argument 1 from ‘std::pair<int, int>’ to ‘long unsigned int&’
  192 |       operator>>(unsigned long& __n)
      |                  ~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/istream:188:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
  188 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/13/istrea...